2002 | OriginalPaper | Chapter
Disjoint Paths and Trees
Authors : Jørgen Bang-Jensen, PhD, Gregory Gutin, MSc, PhD
Published in: Digraphs
Publisher: Springer London
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this chapter we concentrate on problems concerning (arc)-disjoint paths or trees (arborescences). We embark from the 2-path problem which concerns the existence of two disjoint paths with prescribed initial and terminal vertices. We give a proof by Fortune et al. showing that the 2-path problem is NP-complete. We proceed by studying the more general k-path problem for various classes of digraphs. We show that for acyclic digraphs, the k-path problem is polynomially solvable when k is not a part of the input. Then we describe several results on the k-path problem for generalizations of tournaments. Among other results, we show that the 2-path problem is polynomially solvable for digraphs that can be obtained from strong semi-complete digraphs by substituting arbitrary digraphs for each vertex of the semicomplete digraph. We briefly discuss the k-path problem for planar digraphs and indicate how to use the topological concept of planarity in proofs and algorithms for disjoint path problems in planar digraphs.