research
∙
07/24/2023
Knapsack: Connectedness, Path, and Shortest-Path
We study the knapsack problem with graph theoretic constraints. That is,...
share
research
∙
07/01/2023
Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets
The Euclidean Steiner Minimal Tree problem takes as input a set 𝒫 of poi...
research
∙
04/20/2020
Parameterized Study of Steiner Tree on Unit Disk Graphs
We study the Steiner Tree problem on unit disk graphs. Given a n vertex ...
research
∙
06/13/2019
Structural Parameterization for Graph Deletion Problems over Data Streams
The study of parameterized streaming complexity on graph problems was in...
research
∙
06/13/2019
Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
In this work, we initiate a systematic study of parameterized streaming ...
research
∙
05/01/2019
Parameterized Complexity of Conflict-free Graph Coloring
Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-...
research
∙
07/18/2018
An ETH-Tight Exact Algorithm for Euclidean TSP
We study exact algorithms for Euclidean TSP in R^d. In the early 1990s ...
research
∙
07/17/2018
Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
In this paper, we study the query complexity of parameterized decision a...
research
∙
01/10/2018