A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs

DOI10.1007/3-540-57155-8_269zbMath1504.68174OpenAlexW1485876617MaRDI QIDQ5060135

Philip N. Klein, Sairam Subramanian

Publication date: 18 January 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57155-8_269

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Semi-dynamic shortest paths and breadth-first search in digraphs, Fully dynamic maintenance of vertex cover, Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps, Short and Simple Cycle Separators in Planar Graphs

Cites Work

• A note on two problems in connexion with graphs
• Finding small simple cycle separators for 2-connected planar graphs
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item