ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 15(2) (1995)
C.P. Gopalakrishnan and C. Pandu Rangan
Department of Computer Science
Indian Institute of Technology
Madras 600 036, India
The `two paths problem' is stated as follows. Given an undirected graph G =
(V,E) and vertices s1,t1;s2,t2, the
problem is to determine whether or not G admits two vertex-disjoint paths P1
and P2 connecting s1 with t1 and s2
with t2 respectively. In this paper we give a linear (O(|V |+ |E |))
algorithm to solve the above problem on a permutation graph.
Keywords: algorithm, bridge, connectivity, disjoint paths, permutation graph,
two paths problem.
1991 Mathematics Subject Classification: 05C38, 05C85.