COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
From MaRDI portal
Publication:3084692
DOI10.1142/S1793830910000905zbMath1211.68277MaRDI QIDQ3084692
Andrea Ribichini, Giuseppe F. Italiano, Giorgio Ausiello, Paolo Giulio Franciosa
Publication date: 25 March 2011
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20)
Related Items
On resilient graph spanners ⋮ Graph spanners: a tutorial review ⋮ Fault-tolerant approximate shortest-path trees ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners
Cites Work
- Graph spanners in the streaming model: An experimental study
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Selection and sorting with limited storage
- Restrictions of minimum spanner problems
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Graph spanners
- Decomposable searching problems I. Static-to-dynamic transformation
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Additive graph spanners
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Small Stretch Spanners on Dynamic Graphs
