Mark de Berg

activity

20172025

most citedStable Approximation Algorithms for Dominating Set and Independent Set

1 citations · 1 across the 5 of their papers we have counts for

collaborators

5 papers

math.CO2025

On the Diameter of Arrangements of Topological Disks

Aida Abiad, Boris Aronov, Mark de Berg +3

Let $D = {D_{0}, \dots, D_{n - 1}}$ be a set of $n$ topological disks in the plane and let $A := A (D)$ be the arrangement induced by $\mathcal{D}…

cs.DS2024★ 1 cited

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 $k$ -sta…

cs.CG2020

The Online Broadcast Range-Assignment Problem

Mark de Berg, Aleksandar Markovic, Seeun William Umboh

Let $P = {p_{0}, \dots, p_{n - 1}}$ be a set of points in $R^{d}$ , modeling devices in a wireless network. A range assignment assigns a range $r (p_{i})$ to each point $p_{i} \in P$ , t…

cs.CG2018

A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak +2

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to int…

cs.CG2017

The Homogeneous Broadcast Problem in Narrow and Wide Strips

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak

Let $P$ be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $s \in P$ be a given source node. Each node $p$ can transmit information…