Streaming algorithm for graph spanners-single pass and constant processing time per edge
From MaRDI portal
Publication:963343
DOI10.1016/J.IPL.2007.11.001zbMATH Open1186.68590OpenAlexW1966206200MaRDI QIDQ963343FDOQ963343
Authors: Surender Baswana 
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
Cites Work
- Complexity of network synchronization
- On sparse spanners of weighted graphs
- Graph spanners
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Graph distances in the streaming model: the value of space
- Automata, Languages and Programming
- Title not available (Why is that?)
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
Cited In (10)
- Depth First Search in the Semi-streaming Model
- Graph spanners: a tutorial review
- Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Efficient distributed computation of distance sketches in networks
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Online Spanners in Metric Spaces
- Computing graph spanners in small memory: fault-tolerance and streaming
- Intractability of min- and max-cut in streaming graphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
This page was built for publication: Streaming algorithm for graph spanners-single pass and constant processing time per edge
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963343)
