Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments

DOI10.1007/978-3-540-75520-3_54MaRDI QIDQ3527251zbMATH OpenOpenAlexFDO

Authors Camil Demetrescu, Giuseppe F. Italiano, Andrea Ribichini, Giorgio Ausiello, Paolo G. Franciosa

Publication date 25 September 2008

Published in Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75520-3_54

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Small stretch ( , )-spanners in the streaming model
• Graph spanners in the streaming model: An experimental study
• Computing graph spanners in small memory: fault-tolerance and streaming
• Computing graph spanners in small memory: fault-tolerance and streaming
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models

Cited in

(9)

• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Graph distances in the streaming model: the value of space
• Spanners and sparsifiers in dynamic streams
• Computing graph spanners in small memory: fault-tolerance and streaming
• Computing graph spanners in small memory: fault-tolerance and streaming
• Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models
• Graph spanners in the streaming model: An experimental study
• Small stretch ( , )-spanners in the streaming model
• Streaming algorithm for graph spanners-single pass and constant processing time per edge

Describes a project that uses

Uses Software

• spanner

This page was built for publication: Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments

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