A fully dynamic approximation scheme for shortest paths in planar graphs

DOI10.1007/PL00009223zbMath0915.68130OpenAlexW2028558845MaRDI QIDQ1273930

Sairam Subramanian, Philip N. Klein

Publication date: 6 January 1999

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009223

zbMATH Keywords

sparse substitute graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (12)

A survey on combinatorial optimization in dynamic environments ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Distributed distance computation and routing with small messages ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ Unnamed Item ⋮ Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Shortest-path queries in static networks ⋮ Dynamic Approximate Vertex Cover and Maximum Matching ⋮ Unnamed Item ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Unnamed Item

This page was built for publication: A fully dynamic approximation scheme for shortest paths in planar graphs