A linear algorithm for the two paths problem on permutation graphs
C.P. Gopalakrishnan, C. Pandu Rangan (1995)
Discussiones Mathematicae Graph Theory
Similarity:
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.