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

DOI10.1137/1.9781611974331.CH53zbMATH Open1410.68266OpenAlexW4235118266MaRDI QIDQ4575632FDOQ4575632

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Title not available (Why is that?)
• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• As Time Goes By: Reflections on Treewidth for Temporal 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)