Dynamic Algorithms for Graph Spanners

DOI10.1007/11841036_10MaRDI QIDQ5449518zbMATH OpenOpenAlexFDO

Authors Surender Baswana

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11841036_10

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

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

Cited in

(17)

• Dynamic graph stream algorithms in \(o(n)\) space
• Graph spanners: a tutorial review
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Fully dynamic randomized algorithms for graph spanners
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• Fully dynamic spanners with worst-case update time
• The State of the Art in Dynamic Graph Algorithms
• Small Stretch Spanners on Dynamic Graphs
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• Fully dynamic geometric spanners
• Dynamic algorithms for graphs with treewidth 2
• On dynamic shortest paths problems
• Graph spanners in the streaming model: An experimental study
• Small stretch ( , )-spanners in the streaming model

This page was built for publication: Dynamic Algorithms for Graph Spanners

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