Small stretch ( , )-spanners in the streaming model

DOI10.1016/J.TCS.2008.04.022MaRDI QIDQ838152zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Giorgio Ausiello, Paolo G. Franciosa, Giuseppe F. Italiano

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 algorithmsgraph spannersexternal memorystreaming algorithms

Mathematics Subject Classification ID

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

Recommendations

• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Graph spanners in the streaming model: An experimental study
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models
• Computing graph spanners in small memory: fault-tolerance and streaming

Cites work

• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• Additive graph spanners
• An Optimal Synchronizer for the Hypercube
• Automata, Languages and Programming
• Complexity of network synchronization
• Delaunay graphs are almost as good as complete graphs
• Dynamic Algorithms for Graph Spanners
• Graph distances in the streaming model: the value of space
• Graph spanners
• Grid spanners
• Introduction to algorithms
• NP-completeness of minimum spanner problems
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• On sparse spanners of weighted graphs
• Reconstructing the shape of a tree from observed dissimilarity data
• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Small Stretch Spanners on Dynamic Graphs
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• There are planar graphs almost as good as the complete graph

Cited in

(6)

• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Computing graph spanners in small memory: fault-tolerance and streaming
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Computing graph spanners in small memory: fault-tolerance and streaming
• Graph distances in the streaming model: the value of space
• Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q838152)