ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  15(1) (1995)   59-72
DOI: 10.7151/dmgt.1007


C. P. Gopalakrishnan
C. Pandu Rangan

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


In this paper we consider the following problem. Given an undirected graph   G = (V,E)   and vertices   s1,t1;s2,t2, the problem is to determine whether or not   G   admits two edge-disjoint paths   P1 and   P2 connecting   s1 with   t1 and   s2 with   t2, respectively. We give a linear    (O(|V|+|E|))   algorithm to solve this problem on a permutation graph.

Keywords: algorithm, bridge, connectivity, disjoint paths, permutation graph.

1991 Mathematics Subject Classification: 058C85, 05C38


[AKP] K. Arvind, V. Kamakoti, C. Pandu Rangan, Efficient Parallel Algorithms for Permutation Graphs, to appear in Journal of Parallel and Distributed Computing.
[BM 80] J. A. Bondy, U.S.R. Murty, Graph Theory with Applications, (Macmillan Press, 1976).
[C 80] A. Cypher, An approach to the   k   paths problem, Proc. of the 12th STOC (1980) 211-217.
[G 80] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, (Academic Press, 1980).
[F 85] A. Frank, Edge-disjoint paths in planar graphs, J. Combin. Theory (B) 39 (1985) 164-178, doi: 10.1016/0095-8956(85)90046-2.
[GP] C. P. Gopalakrishnan, C. Pandu Rangan, The two paths problem on permutation graphs, (submitted).
[LR 78] A. LaPaugh, R. L. Rievest, The subgraph homeomorphism problem, Proc. of the 10th STOC (1978) 40-50.
[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 graph, J. of the ACM 25 (1978) 1-9, doi: 10.1145/322047.322048.
[RP] P. B. Ramprasad, C. Pandu Rangan, A new linear time algorithm for the two path problem on planar graphs, to appear.
[S 90] A. Schwill, Nonblocking graphs: Greedy algorithms to compute disjoint paths, Proc. of the 7th STACS (1990) 250-262.
[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 83] J. Spinrad, Transitive orientation in   O(n2)   time, Proc. of Fifteenth ACM Symposium on the Theory of Computing (1983) 457-466, doi: 10.1145/800061.808777.
[SP 91] A. Srinivasa Rao, C. Pandu Rangan, Linear algorithms for parity path and two path problems on circular arc graphs, BIT 31 (1991) 182-193.
[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.