Edge-disjoint paths in permutation graphs

C. P. Gopalakrishnan; C. Pandu Rangan

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 1, page 59-72
  • ISSN: 2083-5892

Abstract

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

How to cite

top

C. P. Gopalakrishnan, and C. Pandu Rangan. "Edge-disjoint paths in permutation graphs." Discussiones Mathematicae Graph Theory 15.1 (1995): 59-72. <http://eudml.org/doc/270778>.

@article{C1995,
abstract = {In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this 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; graphic algorithms; edge-disjoint paths},
language = {eng},
number = {1},
pages = {59-72},
title = {Edge-disjoint paths in permutation graphs},
url = {http://eudml.org/doc/270778},
volume = {15},
year = {1995},
}

TY - JOUR
AU - C. P. Gopalakrishnan
AU - C. Pandu Rangan
TI - Edge-disjoint paths in permutation graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 1
SP - 59
EP - 72
AB - In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.
LA - eng
KW - algorithm; bridge; connectivity; disjoint paths; permutation graph; graphic algorithms; edge-disjoint paths
UR - http://eudml.org/doc/270778
ER -

References

top
  1. [AKP] K. Arvind, V. Kamakoti, C. Pandu Rangan, Efficient Parallel Algorithms for Permutation Graphs, to appear in Journal of Parallel and Distributed Computing. 
  2. [BM 80] J. A. Bondy, U.S.R. Murty, Graph Theory with Applications, (Macmillan Press, 1976). 
  3. [C 80] A. Cypher, An approach to the k paths problem, Proc. of the 12th STOC (1980) 211-217. 
  4. [G 80] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, (Academic Press, 1980). 
  5. [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. Zbl0583.05036
  6. [GP] C. P. Gopalakrishnan, C. Pandu Rangan, The two paths problem on permutation graphs, (submitted). Zbl0845.05085
  7. [LR 78] A. LaPaugh, R. L. Rievest, The subgraph homeomorphism problem, Proc. of the 10th STOC (1978) 40-50. 
  8. [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. 
  9. [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. Zbl0365.68026
  10. [RP] P. B. Ramprasad, C. Pandu Rangan, A new linear time algorithm for the two path problem on planar graphs, to appear. 
  11. [S 90] A. Schwill, Nonblocking graphs: Greedy algorithms to compute disjoint paths, Proc. of the 7th STACS (1990) 250-262. 
  12. [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
  13. [S 83] J. Spinrad, Transitive orientation in O(n²) time, Proc. of Fifteenth ACM Symposium on the Theory of Computing (1983) 457-466, doi: 10.1145/800061.808777. 
  14. [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. 
  15. [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.