LIPIcs.FSTTCS.2012.337.pdf
- Filesize: 0.49 MB
- 13 pages
Document
Rerouting shortest paths in planar graphs
Author
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-12-14
Cite As Get BibTex
Paul Bonsma. Rerouting shortest paths in planar graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 337-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.337
Abstract
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.
Subject Classification
Keywords
- shortest path
- rerouting
- reconfiguration problem
- planar graph
- polynomial time
- dynamic programming
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads