ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


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


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

Department of Computer Science
Indian Institute of Technology
Madras 600 036, India


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|2)  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.


[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.