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

dynamic graph algorithmsspanners

Mathematics Subject Classification ID

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

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

(13)

• Graph spanners: a tutorial review
• Improved dynamic graph coloring
• A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
• Local computation algorithms for spanners
• A deamortization approach for dynamic spanner and dynamic maximal matching
• Small Stretch Spanners on Dynamic Graphs
• Dynamic Algorithms for Graph Spanners
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• Online Spanners in Metric Spaces
• Online spanners in metric spaces
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Constant-round spanners and shortest paths in congested clique and MPC

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)