Fully dynamic spanners with worst-case update time

DOI10.4230/LIPICS.ESA.2016.17zbMATH Open1397.05184arXiv1606.07864MaRDI QIDQ4606286FDOQ4606286

Authors: Greg Bodwin, Sebastian Krinninger 

Publication date: 2 March 2018

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

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

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)

Cited In (9)

• Graph spanners: a tutorial review
• Title not available (Why is that?)
• 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)