Small stretch \((\alpha ,\beta )\)-spanners in the streaming model

DOI10.1016/j.tcs.2008.04.022zbMath1191.68819WikidataQ61609541 ScholiaQ61609541MaRDI QIDQ838152

Giorgio Ausiello, Giuseppe F. Italiano, Paolo Giulio Franciosa

Publication date: 21 August 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.04.022

zbMATH Keywords

graph spanners; graph algorithms; streaming algorithms; external memory

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Delaunay graphs are almost as good as complete graphs
• On sparse spanners of weighted graphs
• NP-completeness of minimum spanner problems
• There are planar graphs almost as good as the complete graph
• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Complexity of network synchronization
• Graph spanners
• An Optimal Synchronizer for the Hypercube
• Grid spanners
• Additive graph spanners
• Small Stretch Spanners on Dynamic Graphs
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• Dynamic Algorithms for Graph Spanners
• Automata, Languages and Programming