ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 15(2) (1995)
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.