Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Parameterized Complexity of Spanner Problems with Independent Weights and Lengths
Marius Bächler, Markus Chimani, Henning Jasper
In this paper, the parameterized complexity of the multiplicative -spanner problem with independent weights and lengths on undirected graphs is considered for the first time. Al…
cs.DS2025
Simple Approximations for General Spanner Problems
Fritz Bökler, Markus Chimani, Henning Jasper
Consider a graph with n nodes and m edges, independent edge weights and lengths, and arbitrary distance demands for node pairs. The spanner problem asks for a minimum-weight subgra…
cs.DS2024
Exact Minimum Weight Spanners via Column Generation
Fritz Bökler, Markus Chimani, Henning Jasper +1
Given a weighted graph , a minimum weight -spanner is a least-weight subgraph that preserves minimum distances between all node pairs up to a factor of . Th…