4 papers · 1 filter
Disjoint Tours and the Price of Diversity
Mark de Berg, Andrés López MartÃnez, Frits Spieksma
We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as pos…
Parameterized Complexity of Directed Traveling Salesman Problem
Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes +2
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be vi…
Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
Mark de Berg, Andrés López MartÃnez, Frits Spieksma
We generalize the polynomial-time solvability of -\textsc{Diverse Minimum s-t Cuts} (De Berg et al., ISAAC'23) to a wider class of combinatorial problems whose solution sets hav…
Stable Approximation Algorithms for Dominating Set and Independent Set
Mark de Berg, Arpan Sadhukhan, Frits Spieksma
We study the Dominating set problem and Independent Set Problem for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is -sta…