7 papers
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…
Knapsack on Graphs with Relaxed Neighborhood Constraints
Palash Dey, Ashlesha Hota, Sudeshna Kolay
In the knapsack problems with neighborhood constraints that were studied before, the input is a graph on a set of items, each item h…
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…