3 papers
cs.CC2026
On the Complexity of the Minimum-()-Shortcut Problem
Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt +1
We consider the Minimum-- problem (), where the goal is to find the smallest set of shortcut edges such that every v…
cs.DS2025
Revisiting a Successful Reduction Rule for Dominating Set
Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3
Given a graph with vertices and edges, the DominatingSet problem asks for a set of minimal cardinality such that every vertex either is in …
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 and possible weights typically consisting of positive and negative…