Near-optimal light spanners

DOI10.1137/1.9781611974331.CH63MaRDI QIDQ4575642zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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
• scientific article; zbMATH DE number 7378699 (Why is no real title available?)
• 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)