Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights

Details Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights

2010-08-05

arxiv.org/abs/1008.1048v2

Computer Science

Discrete Mathematics

Main change: corrected proof of the boundary vertex bound

Scientific paper

Let $H$ be a fixed graph and let $G$ be an $H$-minor free $n$-vertex graph with integer edge weights and no negative weight cycles reachable from a given vertex $s$. We present an algorithm that computes a shortest path tree in $G$ rooted at $s$ in $\tilde{O}(n^{4/3}\log L)$ time, where $L$ is the absolute value of the smallest edge weight. The previous best bound was $\tilde{O}(n^{\sqrt{11.5}-2}\log L) = O(n^{1.392}\log L)$. Our running time matches an earlier bound for planar graphs by Henzinger et al.

Affiliated with

Also associated with

No associations

Rating

Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights 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 Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-439134