Efficient algorithms for constructing (1+, )-spanners in the distributed and streaming models

DOI10.1145/1011767.1011791MaRDI QIDQ5501495zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Jian Zhang

Publication date 3 August 2015

Published in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1011767.1011791

zbMATH Keywords

spannerstreaming modelalmost shortest paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Small stretch ( , )-spanners in the streaming model
• Local Computation of Nearly Additive Spanners
• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Additive spanners and \(({\alpha}, {\beta})\)-spanners

Cited in

(9)

• New results for finding common neighborhoods in massive graphs in the data stream model
• Fast deterministic distributed algorithms for sparse spanners
• Multipath spanners via fault-tolerant spanners
• Small stretch ( , )-spanners in the streaming model
• (1 + εΒ) -spanner constructions for general graphs
• Computing almost shortest paths (extended abstract)
• Distributed spanner approximation
• Sublinear fully distributed partition with applications
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models

This page was built for publication: Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models

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