𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge-disjoint paths in planar graphs

✍ Scribed by András Frank

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
989 KB
Volume
39
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Edge-Disjoint (s, t)-Paths in Undir
Edge-Disjoint (s, t)-Paths in Undirected Planar Graphs in Linear Time
✍ Karsten Weihe 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 279 KB

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 fast

Vertex-disjoint paths and edge-disjoint
Vertex-disjoint paths and edge-disjoint branchings in directed graphs
✍ R. W. Whitty 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

A theorem of J. Edmonds states that a directed graph has k edge-disjoint branchings rooted at a vertex r if and only if every vertex has k edge-disjoint paths to r . We conjecture an extension of this theorem to vertex-disjoint paths and give a constructive proof of the conjecture in the case k = 2.

Edge-disjoint paths and cycles in n-edge
Edge-disjoint paths and cycles in n-edge-connected graphs
✍ Andreas Huck 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 826 KB

## Abstract We consider finite undirected loopless graphs __G__ in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal __n__ ≥ 0 with the following property: If __G__ is an __n__‐edge‐connected graph, __s__~1~, ⃛,__s__~k~, __t__~1~, ⃛,__t__~k~ are vertices of __G__, a

Disjoint T-paths in tough graphs
Disjoint T-paths in tough graphs
✍ Tomáš Kaiser 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

## Abstract Let __G__ be a graph and __T__ a set of vertices. A __T‐path__ in __G__ is a path that begins and ends in __T__, and none of its internal vertices are contained in __T__. We define a __T‐path covering__ to be a union of vertex‐disjoint __T__‐paths spanning all of __T__. Concentrating on