Small Stretch Spanners on Dynamic Graphs

DOI10.7155/JGAA.00133MaRDI QIDQ5301398zbMATH OpenOpenAlexFDO

Authors Giuseppe F. Italiano, Giorgio Ausiello, Paolo G. Franciosa

Publication date 19 January 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://eudml.org/doc/55395, http://www.emis.de/journals/JGAA/accepted/2006/AusielloFranciosaItaliano2006.10.2.pdf

zbMATH Keywords

fully dynamic algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms – ESA 2005
• Dynamic Algorithms for Graph Spanners
• Fully dynamic spanners with worst-case update time
• Fully dynamic randomized algorithms for graph spanners
• On dynamic shortest paths problems

Cited in

(12)

• Graph spanners: a tutorial review
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Computing graph spanners in small memory: fault-tolerance and streaming
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Fully dynamic spanners with worst-case update time
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• Dynamic Algorithms for Graph Spanners
• Algorithms – ESA 2005
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Minimizing recourse in an adaptive balls and bins game
• Graph spanners in the streaming model: An experimental study
• Small stretch ( , )-spanners in the streaming model

This page was built for publication: Small Stretch Spanners on Dynamic Graphs

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