4 papers
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots
Eduard Eiben, Robert Ganian, Iyad Kanj +1
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the \textsc{Coordinated Sliding-Motion Planning} (CSMP) problem. In this v…
Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem
Patrick O'Hara, M. S. Ramanujan, Theodoros Damoulas
In many real-world routing problems, decision makers must optimise over sparse graphs such as transportation networks with non-metric costs on the edges that do not obey the triang…
An Exercise in Tournament Design: When Some Matches Must Be Scheduled
Sushmita Gupta, M. S. Ramanujan, Peter Strulo
Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. Algorithms for SE tournament manipulation have been an active topic o…
On Structural Parameterizations of the Edge Disjoint Paths Problem
Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set o…