{"id":"arxiv:1204.5613","kind":"preprint","title":"Rerouting shortest paths in planar graphs","authors":["Paul Bonsma"],"author_count":1,"year":2012,"published":"2012-04-25","venue":null,"cited_by":null,"doi":null,"arxiv_id":"1204.5613","nct_id":null,"source_url":"https://arxiv.org/abs/1204.5613","archive_url":"https://space-kitty.com/papers/arxiv:1204.5613","updated":"2012-04-25","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1204.5613","abstract":"A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the 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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}