Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

User Tools

Site Tools


research:spanner

Minimum Weight Spanners

Spanner Approximations in Practice

Conference Paper
M. Chimani and F. Stutzenstein
Algorithms-ESA 2022, LIPIcs, Volume 244, pp. 37:1-37:15, LZI Dagstuhl, 2022

The linked compressed files below contain readme-Files detailing the formats/contents.

Exact Minimum Weight Spanners via Column Generation

Conference Paper
F. Bökler, M. Chimani, H. Jasper and M. H. Wagner
Algorithms-ESA 2024, LIPIcs, Volume 308, pp. 30:1-30:17, LZI Dagstuhl, 2024

The linked compressed files below contain readme-Files detailing the formats/contents.

  • the considered instances including
    • generated instances (Erdos-Renyi, Waxman, Complete),
    • established instances (Road, SteinLib, Edge-Path Bundling),
    • and the parameters used to generate Waxman graphs
  • all experimental data used and reported on in our paper
  • provisional access to our implementations. These will be properly integrated and part of the next release of the free open source C++ library Open Graph algorithms and Datastructures Framework.

Simple Approximations for General Spanner Problems

Conference Paper
F. Bökler, M. Chimani, and H. Jasper
Approximations and Online Algorithms (WAOA) 2025, LNCS, Volume 16077, pp. 48-63, Springer Nature Switzerland, 2025

General Multiplicative Spanners in Practice

Conference Paper
F. Bökler, M. Chimani, and H. Jasper
Symposium on Experimental Algorithms (SEA) 2026, LIPIcs, Volume 371, pp. 8:1-8:21, LZI Dagstuhl, 2026

The linked compressed files below contain readme-Files detailing the formats/contents.

  • the considered instances including
    • generated instances (Erdos-Renyi, Geometric, Orb-Web),
    • real-world instances (Power, Road, Repetita, SteinLib, Stochastic-Block-Model, Edge-Path Bundling),
  • all experimental data used and reported on in our paper
  • provisional access to our implementations. These will be properly integrated and part of the next release of the free open source C++ library Open Graph algorithms and Datastructures Framework.

Multiobjective Spanners

Complexity of the Multiobjective Minimum Weight Minimum Stretch Spanner Problem

Journal Article
F. Bökler and H. Jasper
MMOR 100, pp. 65–83, Springer, 2024

research/spanner.txt · Last modified: by jasper