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/