| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419790 | Discrete Applied Mathematics | 2009 | 8 Pages |
Abstract
Given a number of requests ℓℓ, we propose a polynomial-time algorithm for finding ℓℓ disjoint paths in a symmetric directed graph. It is known that the problem of finding ℓ≥2ℓ≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111–121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65–110] to check the feasibility of each configuration.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
A. Jarry, S. Pérennes,