𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge-Disjoint (s, t)-Paths in Undirected Planar Graphs in Linear Time

✍ Scribed by Karsten Weihe

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
279 KB
Volume
23
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the following problem. Let G s V, E be an undirected planar graph and let s, t g V, s / t. The problem is to find a set of pairwise edge-disjoint paths in G, each connecting s with t, of 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 O V log V . We give a linear time algorithm in this paper. ᮊ 1997 Academic Press * This work was supported by the Technische Universitat Berlin under Grant FIP 1r3 and by the Deutsche Forschungsgemeinschaft under Grant Wa 654r10-2. A preliminary version has been published under the same title in ''Proceedings of the Second European Symposium Ž .

📜 SIMILAR VOLUMES

Edge disjoint Hamilton cycles in sparse
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for