4 papers
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…
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…
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…
Complexity of the Multiobjective Spanner Problem
Fritz Bökler, Henning Jasper
In this paper, we take an in-depth look at the complexity of a hitherto unexplored Multiobjective Spanner (MSp) problem. The MSp is a multiobjective generalization of the well-stud…