3 citations · 3 across the 4 of their papers we have counts for
6 papers
On Linear-Size Guillotine-Separable Subsets of Fat Convex Objects, Disks, and Squares
Mark de Berg, Debajyoti Kar, Arindam Khan +1
Let be a family of pairwise disjoint objects in the plane. We say that a subset is \emph{separable} if it admits a sequence of gu…
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…
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
Peyman Afshani, Mark De Berg, Kevin Buchin +7
We consider the problem of finding patrol schedules for robots to visit a given set of sites in a metric space. Each robot has the same maximum speed and the goal is to min…