Rerouting shortest paths in planar graphs

Details Rerouting shortest paths in planar graphs Rerouting shortest paths in planar graphs

2012-04-25

arxiv.org/abs/1204.5613v1

Computer Science

Data Structures and Algorithms

submitted

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Rerouting shortest paths in planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rerouting shortest paths in planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rerouting shortest paths in planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137754