Fully dynamic spanners with worst-case update time

DOI10.4230/LIPICS.ESA.2016.17MaRDI QIDQ4606286zbMATH OpenFDO

Authors Greg Bodwin, Sebastian Krinninger

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1606.07864

zbMATH Keywords

spannersdynamic graph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Distance in graphs (05C12)

Recommendations

• Dynamic Algorithms for Graph Spanners
• Small Stretch Spanners on Dynamic Graphs
• Algorithms – ESA 2005
• Fully dynamic randomized algorithms for graph spanners
• A deamortization approach for dynamic spanner and dynamic maximal matching

Cited in

(9)

• Graph spanners: a tutorial review
• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• Small Stretch Spanners on Dynamic Graphs
• A deamortization approach for dynamic spanner and dynamic maximal matching
• Dynamic Algorithms for Graph Spanners
• Algorithms – ESA 2005
• Online Spanners in Metric Spaces
• Local computation algorithms for spanners
• Improved dynamic graph coloring

This page was built for publication: Fully dynamic spanners with worst-case update time

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