Streaming algorithm for graph spanners-single pass and constant processing time per edge
From MaRDI portal
Publication:963343
DOI10.1016/j.ipl.2007.11.001zbMath1186.68590MaRDI QIDQ963343
Publication date: 19 April 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.001
Related Items
Distributed algorithms for ultrasparse spanners and linear size skeletons, Intractability of min- and max-cut in streaming graphs, COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On sparse spanners of weighted graphs
- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
- Complexity of network synchronization
- Graph spanners
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
- Automata, Languages and Programming
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques