4 papers
Collective Graph Exploration Parameterized by Vertex Cover
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
We initiate the study of the parameterized complexity of the {\sc Collective Graph Exploration} ({\sc CGE}) problem. In {\sc CGE}, the input consists of an undirected connected gra…
Drawn Tree Decomposition: New Approach for Graph Drawing Problems
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
Over the past decade, we witness an increasing amount of interest in the design of exact exponential-time and parameterized algorithms for problems in Graph Drawing. Unfortunately,…
Grid Recognition: Classical and Parameterized Computational Perspectives
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
Grid graphs, and, more generally, grid graphs, form one of the most basic classes of geometric graphs. Over the past few decades, a large body of works studied the (in)…
The Parameterized Complexity of Motion Planning for Snake-Like Robots
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial posi…