Multiple-Source Shortest Paths in Embedded Graphs

Details Multiple-Source Shortest Paths in Embedded Graphs Multiple-Source Shortest Paths in Embedded Graphs

2012-02-01

arxiv.org/abs/1202.0314v1

Computer Science

Data Structures and Algorithms

25 pages, 3 figures. Submitted to SIAM Journal on Computing. Preliminary version, without the third author's contributions, in

Scientific paper

Let G be a directed graph with n vertices and non-negative weights in its directed edges, embedded on a surface of genus g, and let F be an arbitrary face of G. We describe an algorithm to preprocess the graph in O(gn log n) time, so that the shortest-path distance from any vertex on the boundary of F to any other vertex in G can be retrieved in O(log n) time. Our result directly generalizes the O(n log n)-time algorithm of Klein [SODA 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of F. As an application of our algorithm, we describe algorithms to compute a shortest non-contractible or non-separating cycle in embedded, undirected graphs in O(g^2 n log n) time.

Affiliated with

Also associated with

No associations

Rating

Multiple-Source Shortest Paths in Embedded 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 Multiple-Source Shortest Paths in Embedded Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple-Source Shortest Paths in Embedded Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-186479