A linear algorithm for the two paths problem on permutation graphs

C.P. Gopalakrishnan; C. Pandu Rangan

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 2, page 147-166
  • ISSN: 2083-5892

Abstract

top
The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

How to cite

top

C.P. Gopalakrishnan, and C. Pandu Rangan. "A linear algorithm for the two paths problem on permutation graphs." Discussiones Mathematicae Graph Theory 15.2 (1995): 147-166. <http://eudml.org/doc/270239>.

@article{C1995,
abstract = {The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.},
author = {C.P. Gopalakrishnan, C. Pandu Rangan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {algorithm; bridge; connectivity; disjoint paths; permutation graph; two paths problem},
language = {eng},
number = {2},
pages = {147-166},
title = {A linear algorithm for the two paths problem on permutation graphs},
url = {http://eudml.org/doc/270239},
volume = {15},
year = {1995},
}

TY - JOUR
AU - C.P. Gopalakrishnan
AU - C. Pandu Rangan
TI - A linear algorithm for the two paths problem on permutation graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 2
SP - 147
EP - 166
AB - The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.
LA - eng
KW - algorithm; bridge; connectivity; disjoint paths; permutation graph; two paths problem
UR - http://eudml.org/doc/270239
ER -

References

top
  1. [BM 76] J.A. Bondy, U.S.R. Murthy, Graph Theory with Applications (Academic Press, 1976). 
  2. [ET 75] S. Even, R.E. Tarjan, Network flow and testing graph connectivity, SIAM J. Comput. 4 (1975) 507-518, doi: 10.1137/0204043. Zbl0328.90031
  3. [HT 74] J.E. Hopcroft, R.E. Tarjan, Efficient planarity testing, J. ACM 21 (1974) 549-568, doi: 10.1145/321850.321852. Zbl0307.68025
  4. [G 80] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980). 
  5. [MT 89] B. Mishra, R.E. Tarjan, A linear time algorithm for finding an ambitus (Technical Report 464, August 1989, New York University). 
  6. [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. 
  7. [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. Zbl0365.68026
  8. [RP] P.B. Ramprasad, C. Pandu Rangan, A new linear time algorithm for the two path problem on planar graphs (Technical Report, Department of Computer Science, IIT, Madras, 1991). 
  9. [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. Zbl0475.68042
  10. [S 83] J. Spinrad, Transitive orientation in O(n²) time, In: Proc. of Fifteenth ACM Symposium on the Theory of Computing (1983) 457-466, doi: 10.1145/800061.808777. 
  11. [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). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.