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/