2 citations · 8 across the 8 of their papers we have counts for
18 papers
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
Mark de Berg, Sándor Kisfaludi-Bak
Recently it was shown that many classic graph problems -- Independent Set, Dominating Set, Hamiltonian Cycle, and more -- can be solved in subexponential time on unit-ball graphs.…
A Note on Reachability and Distance Oracles for Transmission Graphs
Mark de Berg
Let be a set of points in the plane, where each point has a transmission radius . The transmission graph defined by and the given radii, denoted by $\m…
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady, Mark de Berg, Karl Bringmann +6
We consider the unlabeled motion-planning problem of unit-disc robots moving in a simple polygonal workspace of edges. The goal is to find a motion plan that moves the robo…
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
Peyman Afshani, Mark de Berg, Kevin Buchin +7
We consider the following surveillance problem: Given a set of sites in a metric space and a set of robots with the same maximum speed, compute a patrol schedule of min…
-Center Clustering with Outliers in the Sliding-Window Model
Mark de Berg, Morteza Monemizadeh, Yu Zhong
The -center problem for a point set~ asks for a collection of congruent balls (that is, balls of equal radius) that together cover all the points in and whose radius…
Rectilinear Steiner Trees in Narrow Strips
Henk Alkema, Mark de Berg
A rectilinear Steiner tree for a set of points in is a tree that connects the points in using horizontal and vertical line segments. The goal of Minimal Rect…