Efficient algorithms for constructing very sparse spanners and emulators

DOI10.1137/1.9781611974782.41MaRDI QIDQ4575779zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Ofer Neiman

Publication date 16 July 2018

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

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

Mathematics Subject Classification ID

Distance in graphs (05C12) Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Efficient algorithms for constructing very sparse spanners and emulators
• Fast deterministic distributed algorithms for sparse spanners
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• On the locality of distributed sparse spanner construction
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models

Cited in

(15)

• Local algorithms for sparse spanning graphs
• Property testing of planarity in the \textsf{CONGEST} model
• Very sparse additive spanners and emulators
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• Efficient algorithms for constructing very sparse spanners and emulators
• The greedy spanner is existentially optimal
• Distributed spanner approximation
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• Fast Distributed Approximation for Max-Cut
• Local computation algorithms for spanners
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• A unified framework for light spanners
• Exact minimum weight spanners via column generation
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

This page was built for publication: Efficient algorithms for constructing very sparse spanners and emulators

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