Alexander Leonhardt

activity

20242026

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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…

cs.DS2024

Insights into $(k, I ¨ )$ -shortcutting algorithms

Alexander Leonhardt, Ulrich Meyer, Manuel Penschuck

A graph is called a $(k, I ¨ )$ -graph iff every node can reach $I ¨ $ of its nearest neighbors in at most k hops. This property proved useful in the analysis and design of parallel shor…

Revisiting a Successful Reduction Rule for Dominating Set

Efficient Uniform Negative Edge Weights

Insights into (k,I¨)-shortcutting algorithms

Insights into $(k, I ¨ )$ -shortcutting algorithms