Disjoint paths in tournaments
Given k pairs of vertices (si, ti) (1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more general...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2014
|