Lukas Retschmeier

collaborators

5 papers

cs.DS2025

Revisiting a Successful Reduction Rule for Dominating Set

Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3

Given a graph $G = (V, E)$ with $n$ vertices and $m$ edges, the DominatingSet problem asks for a set $D \subseteq V$ of minimal cardinality such that every vertex either is in $D$ …

cs.CC2025

On the Parameterized Complexity of Semitotal Domination on Graph Classes

Lukas Retschmeier

For a given graph $G = (V, E)$ , a subset of the vertices $D \subseteq V$ is called a semitotal dominating set, if $D$ is a dominating set and every vertex $v \in D$ is within distan…

cs.CR2025

Private Lossless Multiple Release

Joel Daniel Andersson, Lukas Retschmeier, Boel Nelson +1

Koufogiannis et al. (2016) showed a $gradual release$ result for Laplace noise-based differentially private mechanisms: given an $ε$ -DP release, a new release wi…

cs.DS2024

The Correlated Gaussian Sparse Histogram Mechanism

Christian Janos Lebeda, Lukas Retschmeier

We consider the problem of releasing a sparse histogram under $(ε, I^´)$ -differential privacy. The stability histogram independently adds noise from a Laplace or Gaussian…

cs.DS2024

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation

Rasmus Pagh, Lukas Retschmeier, Hao Wu +1

We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph $G = (V, E, W)$ where $V$ is a set of $n$ vertices, $E$ is a set of $m$ …