DMGT

Discussiones Mathematicae Graph Theory 15(2) (1995) 119-145
DOI: https://doi.org/10.7151/dmgt.1012

EFFICIENT ALGORITHMS FOR MINIMAL DISJOINT PATH PROBLEMS ON CHORDAL GRAPHS

C.P. Gopalakrishnan, C.R. Satyan and C. Pandu Rangan

Department of Computer Science
Indian Institute of Technology
Madras 600 036, India
email: rangan@iitm.ernet.in

Abstract

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.

1991 Mathematics Subject Classification: 05C38, 05C85.

References

[G 80]	M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980).
[K 75]	R.M. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45-68.
[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.
[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.
[RS 86]	N. Robertson, P.D. Seymour, Graph minors XIII. The disjoint paths problem, Manuscript 1986.
[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.
[S 89]	A. Schwill, Shortest edge-disjoint paths in graphs, in: Proc. of the 6th STACS (1989) 505-516.
[S 90]	A. Schwill, Nonblocking graphs: Greedy algorithms to compute disjoint paths, in: Proc. of the 7th STACS (1990) 250-262.
[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.