10 papers
On the Largest Cardinality Subset Sum
Deepak Bhati, Anubhav Dhar, Pranjal Dutta +2
We study Largest Cardinality Subset Sum (LCSS): given nonnegative integers and a target , compute a subset summing to with maximum cardinality. We also consider its all-…
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
Faster Exponential Algorithms for Multi-Machine Scheduling Problems
Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2
Minimizing the weighted completion times () and weighted number of tardy jobs () on multiple identical machines are two classical NP-har…
On Euler Paths and the Maximum Degree Growth of Iterated Higher Order Line Graphs
Aryan Sanghi, Anubhav Dhar, Sudeshna Kolay
Given a simple graph , its line graph, denoted by , is obtained by representing each edge of as a vertex, with two vertices in adjacent whenever the correspondi…
Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
Palash Dey, Anubhav Dhar, Ashlesha Hota +2
In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs and a non-negative integer , is there a common subgraph on at least …
Universal Solvability for Robot Motion Planning on Graphs
Anubhav Dhar, Pranav Nyati, Tanishq Prasad +2
We study the Universal Solvability of Robot Motion Planning on Graphs (USolR) problem: given an undirected graph and robots, determine whether any arbitrary config…
Minimizing Envy and Maximizing Happiness in Graphical House Allocation
Anubhav Dhar, Ashlesha Hota, Palash Dey +1
We study the house allocation problem in a setting where agents are connected by a graph representing friendships. In this model, two agents can only envy each other if they are ne…
Local problems in trees across a wide range of distributed models
Anubhav Dhar, Eli Kujawa, Henrik Lievonen +4
The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algori…
Efficient Exact Algorithms for Minimum Covering of Orthogonal Polygons with Squares
Anubhav Dhar, Subham Ghosh, Sudeshna Kolay
Let be an orthogonal polygon of vertices, without holes. The Orthogonal Polygon Covering with Squares (OPCS) problem takes as input such an orthogonal polygon with inte…
Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets
Anubhav Dhar, Soumita Hait, Sudeshna Kolay
The Euclidean Steiner Minimal Tree problem takes as input a set of points in the Euclidean plane and finds the minimum length network interconnecting all the points of…