Computing graph spanners in small memory: fault-tolerance and streaming
DOI10.1142/S1793830910000905zbMATH Open1211.68277MaRDI QIDQ3084692FDOQ3084692
Authors: Andrea Ribichini, Giuseppe F. Italiano, Giorgio Ausiello, Paolo G. Franciosa 
Publication date: 25 March 2011
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Recommendations
- Computing graph spanners in small memory: fault-tolerance and streaming
- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
- Fault-tolerant spanners for general graphs
- Fault tolerant spanners for general graphs
Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)
Cites Work
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Additive graph spanners
- Small Stretch Spanners on Dynamic Graphs
- Graph spanners in the streaming model: An experimental study
- Decomposable searching problems I. Static-to-dynamic transformation
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Selection and sorting with limited storage
- Restrictions of minimum spanner problems
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
Cited In (8)
- Graph spanners: a tutorial review
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
- Computing graph spanners in small memory: fault-tolerance and streaming
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Space lower bounds for graph stream problems
- Graph spanners in the streaming model: An experimental study
- Fault-tolerant approximate shortest-path trees
- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
This page was built for publication: Computing graph spanners in small memory: fault-tolerance and streaming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3084692)
