7 papers
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…
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 …
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…
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…