Geodesic
Efficient algorithms for minimal disjoint path problems on chordal graphs
Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 119-145.

Voir la notice de l'article provenant de la source Library of Science

Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an O(|V| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |E|) algorithm for 2 vertex disjoint paths and an O(|V|+|E|) algorithm for 2 edge disjoint paths, which is a significant improvement over the previous result.
Keywords: chordal graph, minimal paths, disjoint paths, clique, bfs 
@article{DMGT_1995_15_2_a1,
     author = {Gopalakrishnan, C. and Satyan, C. and Pandu Rangan, C.},
     title = {Efficient algorithms for minimal disjoint path problems on chordal graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {119--145},
     publisher = {mathdoc},
     volume = {15},
     number = {2},
     year = {1995},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a1/}
}
TY  - JOUR
AU  - Gopalakrishnan, C.
AU  - Satyan, C.
AU  - Pandu Rangan, C.
TI  - Efficient algorithms for minimal disjoint path problems on chordal graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1995
SP  - 119
EP  - 145
VL  - 15
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a1/
LA  - en
ID  - DMGT_1995_15_2_a1
ER  - 
%0 Journal Article
%A Gopalakrishnan, C.
%A Satyan, C.
%A Pandu Rangan, C.
%T Efficient algorithms for minimal disjoint path problems on chordal graphs
%J Discussiones Mathematicae. Graph Theory
%D 1995
%P 119-145
%V 15
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a1/
%G en
%F DMGT_1995_15_2_a1
Gopalakrishnan, C.; Satyan, C.; Pandu Rangan, C. Efficient algorithms for minimal disjoint path problems on chordal graphs. Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 119-145. http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a1/

[1] [G 80] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980).

[2] [K 75] R.M. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45-68.

[3] [O 80] T. Ohtsuki, The two disjoint path problem and wire routing design, in: Proc. of the 17th Symp. of Res. Inst. of Electrical Comm. (1980) 257-267.

[4] [PS 78] Y. Perl, Y. Shiloach, Finding two disjoint paths between two pairs of vertices in a graph, J. of the ACM 25 (1978) 1-9, doi: 10.1145/322047.322048.

[5] [RS 86] N. Robertson, P.D. Seymour, Graph minors XIII. The disjoint paths problem, Manuscript 1986.

[6] [S 80] Y. Shiloach, A polynomial solution to the undirected two paths problem, J. of the ACM 27 (1980) 445-456, doi: 10.1145/322203.322207.

[7] [S 89] A. Schwill, Shortest edge-disjoint paths in graphs, in: Proc. of the 6th STACS (1989) 505-516.

[8] [S 90] A. Schwill, Nonblocking graphs: Greedy algorithms to compute disjoint paths, in: Proc. of the 7th STACS (1990) 250-262.

[9] [KPS 91] S.V. Krishnan, C. Pandu Rangan, S. Seshadri, A. Schwill, Two Disjoint Paths in Chordal graphs, Technical report, 2/91, February 1991, University of Oldenburg, Germany.