Near-optimal light spanners

DOI10.1137/1.9781611974331.CH63zbMATH Open1410.05035OpenAlexW4229802563MaRDI QIDQ4575642FDOQ4575642

Authors: Shiri Chechik, Christian Wulff-Nilsen 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch63

Recommendations

• Near-optimal light spanners
• Light spanners
• Light spanners
• Fast constructions of light-weight spanners for general graphs
• Fast constructions of lightweight spanners for general graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Signed and weighted graphs (05C22)

Cited In (17)

• Light spanners in bounded pathwidth graphs
• Near-optimal light spanners
• Light spanners
• Light spanners
• The greedy spanner is existentially optimal (extended abstract)
• Fast constructions of lightweight spanners for general graphs
• Fast constructions of light-weight spanners for general graphs
• Truly Optimal Euclidean Spanners
• Title not available (Why is that?)
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Algorithms – ESA 2004
• On additive spanners in weighted graphs with local error
• A unified framework for light spanners
• Light Euclidean Spanners with Steiner Points
• The greedy spanner is existentially optimal
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• Spanning spiders and light-splitting switches

This page was built for publication: Near-optimal light spanners

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