Fast constructions of light-weight spanners for general graphs

DOI10.1137/1.9781611973105.37MaRDI QIDQ5741745zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Shay Solomon

Publication date 15 May 2019

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

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

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

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

Cited in

(10)

• A fast algorithm for source-wise round-trip spanners
• Constructing light spanners deterministically in near-linear time
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-optimal light spanners
• Near-optimal light spanners
• Fast constructions of lightweight spanners for general graphs
• Constructing Light Spanners Deterministically in Near-Linear Time
• (1 + εΒ) -spanner constructions for general graphs
• Light spanners

This page was built for publication: Fast constructions of light-weight spanners for general graphs

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