Lukas Geis

collaborators

2 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.DS2024

Efficient Uniform Negative Edge Weights

Lukas Geis, Daniel Allendorf, Thomas BlÃ¤sius +4

We consider a maximum entropy edge weight model that allows for negative weights. Given a graph $G$ and possible weights $W$ typically consisting of positive and negative…