Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.DS2017
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…