[+] Shortest paths with negative lengths in minorfree graphs. 
We revisit the shortest paths problem, considering the case where the input is a directed minorfree graph with negative arc lengths (but no negativelength cycles). In Lecture 14, we saw almostlineartime algorithms for the case of planar and boundedgenus graphs. Currently, comparable bounds for minorfree graphs are not known. We shall discuss Goldberg's algorithm, a shortestpath algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minorfree graphs than on general graphs, but it still requires superlinear time. 
Lecture notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/7 • [previous page] • [next page] • [PDF] 

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.