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

DOI10.1016/j.tcs.2008.04.022zbMath1191.68819OpenAlexW2067528822WikidataQ61609541 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 spannersgraph algorithmsstreaming algorithmsexternal memory

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

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

This page was built for publication: Small stretch \((\alpha ,\beta )\)-spanners in the streaming model