𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint paths in a network

✍ Scribed by J. W. Suurballe

Publisher
John Wiley and Sons
Year
1974
Tongue
English
Weight
931 KB
Volume
4
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximations for the Disjoint Paths Pr
Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks
✍ Jon Kleinberg; Γ‰va Tardos πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 512 KB

We consider the problem of connecting distinguished terminal pairs in a graph via edge-disjoint paths. This is a classical NP-complete problem for which no general approximation techniques are known; it has recently been brought into focus in papers discussing applications to admission control in hi

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

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.