𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint Paths in Graphs III, Characterization

✍ Scribed by Xingxing Yu

Publisher
Springer
Year
2003
Tongue
English
Weight
326 KB
Volume
7
Category
Article
ISSN
0218-0006

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

Short Disjoint Paths in Locally Connecte
Short Disjoint Paths in Locally Connected Graphs
✍ Chuanping Chen; Roman Čada; TomΓ‘Ε‘ Kaiser; ZdenΔ›k RyjÑček πŸ“‚ Article πŸ“… 2007 πŸ› Springer Japan 🌐 English βš– 185 KB
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.

Node-to-set disjoint paths problem in st
Node-to-set disjoint paths problem in star graphs
✍ Qian-Ping Gu; Shietung Peng πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 567 KB

GivenanodesandasetZ'={t~,..., tk} of k nodes in a k-connected graph, the node-to-set disjoint paths problem is to find k node-disjoint paths pi : s -+ ti, 1 < i < k. In this paper, we give two O(n\*) time algorithms for the node-to-set disjoint paths problem in n-dimensional star graphs G, which are