COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING

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)

zbMATH Keywords

graph spannersfault toleranceexternal memorydata streaming

Mathematics Subject Classification ID

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