Streaming algorithm for graph spanners-single pass and constant processing time per edge

DOI10.1016/J.IPL.2007.11.001zbMath1186.68590OpenAlexW1966206200MaRDI QIDQ963343

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

zbMATH Keywords

shortest pathanalysis of algorithmson-line algorithmsspannerstreaming

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Online Spanners in Metric Spaces ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING ⋮ Efficient distributed computation of distance sketches in networks ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Depth First Search in the Semi-streaming Model ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

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

This page was built for publication: Streaming algorithm for graph spanners-single pass and constant processing time per edge