Computing graph spanners in small memory: fault-tolerance and streaming

DOI10.1142/S1793830910000905MaRDI QIDQ3084692zbMATH OpenFDO

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)

zbMATH Keywords

fault tolerancegraph spannersexternal memorydata streaming

Mathematics Subject Classification ID

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)

Recommendations

• Computing graph spanners in small memory: fault-tolerance and streaming
• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Small stretch ( , )-spanners in the streaming model
• Fault-tolerant spanners for general graphs
• Fault tolerant spanners for general graphs

Cites work

• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Additive graph spanners
• Decomposable searching problems I. Static-to-dynamic transformation
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Graph spanners
• Graph spanners in the streaming model: An experimental study
• Restrictions of minimum spanner problems
• Selection and sorting with limited storage
• Small Stretch Spanners on Dynamic Graphs
• Small stretch ( , )-spanners in the streaming model
• Streaming algorithm for graph spanners-single pass and constant processing time per edge

Cited in

(8)

• Graph spanners: a tutorial review
• Small stretch ( , )-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)