Spanner approximations in practice

DOI10.4230/LIPICS.ESA.2022.37MaRDI QIDQ6969646zbMATH OpenFDO

Authors Markus Chimani, Finn Stutzenstein

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.37

zbMATH Keywords

algorithm engineeringexperimental studygraph spanners

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A Fast Parametric Maximum Flow Algorithm and Applications
• A framework for computing the greedy spanner
• A new approach to the maximum-flow problem
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• A trade-off between space and efficiency for routing tables
• Algorithms – ESA 2004
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Approximate distance oracles
• Approximating \(k\)-spanner problems for \(k>2\)
• Approximating low-stretch spanners
• Approximation algorithms for spanner problems and directed Steiner forest
• Compact roundtrip routing in directed networks
• Compact routing with minimum stretch
• Complexity of network synchronization
• Constructing Light Spanners Deterministically in Near-Linear Time
• Efficient algorithms for constructing very sparse spanners and emulators
• Experimental study of geometric \(t\)-spanners
• Fast constructions of lightweight spanners for general graphs
• Generating Sparse 2-Spanners
• Graph spanners
• Graph spanners: a tutorial review
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 1420896 (Why is no real title available?)
• Light spanners
• NP-completeness of minimum spanner problems
• On dynamic shortest paths problems
• On sparse spanners of weighted graphs
• Spanner approximations in practice
• Testing and reconstruction of Lipschitz functions with applications to data privacy
• Transitive-closure spanners
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(4)

• Simple approximations for general spanner problems
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
• Spanner approximations in practice
• Exact minimum weight spanners via column generation

This page was built for publication: Spanner approximations in practice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969646)