On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

DOI10.1137/1.9781611974331.CH53MaRDI QIDQ4575632zbMATH OpenOpenAlexFDO

Authors Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch53

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A fully dynamic approximation scheme for shortest paths in planar graphs
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• Dynamic algorithms for shortest paths in planar graphs
• scientific article; zbMATH DE number 219245
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• On dynamic shortest paths problems
• Algorithms – ESA 2004

Cited in

(7)

• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Fine-grained complexity lower bounds for families of dynamic graphs

This page was built for publication: On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

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