3 citations · 3 across the 4 of their papers we have counts for
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…
An Algorithm for Single-Source Shortest Paths in Disk Graphs
Mark de Berg, Sergio Cabello
We prove that the single-source shortest-path problem on disk graphs can be solved in time, and that it can be solved on intersection graphs of fat triangles in $O(n\l…
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…