Technical Report 374-1994
- Title
- Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
- Author
- Publication
- Proc. 2nd Annual Europ. Symp. Algorithms (ESA '94), ed. J.v.Leeuwen, 1994, pp. 130-140
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
We consider the following problem. Let G=(V,E) be an undirected planar graph and let s,t&; V, `s eq t`. The problem is to find a set of pairwise edge-disjoint paths, each connecting s with t, with maximum cardinality. In other words, the problem is to find a maximum unit flow from s to t. The fastest algorithm in the literature has running time O(|V|log|V|). In this paper now, we give a linear time algorithm.