Publikationsansicht

Faster Shortest-Path Algorithms for Planar Graphs (1994)

Abstract

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiring O(n 4=3 log(nL)) time, where L is the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms. 1 Introduction Computing shortest paths is a fundamental and ubiquitous problem in network analysis. Aside from the importance of this problem in its own right, often the problem arises in the solution of other problems (e.g. network flow and matching). In thi...

Details der Publikation

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=?doi=10.1.1.39.1759
Quelle	http://www.cs.brown.edu/people/pnk/sepshort.ps
Mitarbeiter	CiteSeerX
Archiv	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Typ	text
Sprache	Englisch
Verknüpfungen	10.1.1.23.7975, 10.1.1.30.3705, 10.1.1.56.2239, 10.1.1.24.538, 10.1.1.5.5213, 10.1.1.100.7360, 10.1.1.3.7229, 10.1.1.54.2037, 10.1.1.131.1157, 10.1.1.16.4608, 10.1.1.25.6957, 10.1.1.106.810, 10.1.1.32.9856, 10.1.1.124.9963, 10.1.1.132.4925, 10.1.1.33.1630, 10.1.1.54.512, 10.1.1.116.8924, 10.1.1.47.1107, 10.1.1.60.3398, 10.1.1.56.824, 10.1.1.34.4668, 10.1.1.28.4903, 10.1.1.130.6484, 10.1.1.100.2138, 10.1.1.107.3390, 10.1.1.115.3559, 10.1.1.35.9074, 10.1.1.17.6526, 10.1.1.53.7790, 10.1.1.1.6936, 10.1.1.32.1501, 10.1.1.6.4172, 10.1.1.98.7446, 10.1.1.48.3605, 10.1.1.102.3701, 10.1.1.42.6848, 10.1.1.60.4287, 10.1.1.64.5547, 10.1.1.74.6826, 10.1.1.132.8043, 10.1.1.23.4817, 10.1.1.1.1862, 10.1.1.106.8879, 10.1.1.67.2260, 10.1.1.134.7156, 10.1.1.137.8576, 10.1.1.139.628, 10.1.1.139.4736, 10.1.1.1.9747, 10.1.1.100.3534, 10.1.1.101.5900, 10.1.1.102.7046, 10.1.1.103.4147, 10.1.1.103.6911, 10.1.1.104.5934, 10.1.1.105.6893, 10.1.1.107.8086, 10.1.1.108.1595, 10.1.1.26.4291, 10.1.1.30.2879, 10.1.1.62.7834, 10.1.1.64.622, 10.1.1.64.8814, 10.1.1.67.3587, 10.1.1.74.9858, 10.1.1.83.6392, 10.1.1.83.9371, 10.1.1.85.5964, 10.1.1.86.8944, 10.1.1.88.3515, 10.1.1.89.3452, 10.1.1.89.6441, 10.1.1.92.2325, 10.1.1.92.8120, 10.1.1.93.3835, 10.1.1.94.6917, 10.1.1.95.8231, 10.1.1.98.1645, 10.1.1.99.1103, 10.1.1.113.1366, 10.1.1.114.9602, 10.1.1.115.3882, 10.1.1.116.5858, 10.1.1.121.7725, 10.1.1.123.4409, 10.1.1.131.5963, 10.1.1.133.9481, 10.1.1.136.6094, 10.1.1.139.5818, 10.1.1.55.5500, 10.1.1.56.3597, 10.1.1.45.8381, 10.1.1.29.5454, 10.1.1.22.1476, 10.1.1.22.7128, 10.1.1.13.2050, 10.1.1.9.5574