Gopalakrishnan, C. P.; Pandu Rangan, C. A linear algorithm for the two paths problem on permutation graphs. (English) Zbl 0845.05085 Discuss. Math., Graph Theory 15, No. 2, 147-166 (1995). Summary: The two paths problem is stated as follows. Given an undirected graph \(G = (V,E)\) and vertices \(s_1, t_1; s_2, t_2\), the problem is to determine whether or not \(G\) admits two vertex-disjoint paths \(P_1\) and \(P_2\) connecting \(s_1\) with \(t_1\) and \(s_2\) with \(t_2\) respectively. In this paper we give a linear \(O (|V |+ |E |)\) algorithm to solve the above problem on a permutation graph. MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles Keywords:bridge; connectivity; disjoint paths; two paths problem; algorithm; permutation graph PDFBibTeX XMLCite \textit{C. P. Gopalakrishnan} and \textit{C. Pandu Rangan}, Discuss. Math., Graph Theory 15, No. 2, 147--166 (1995; Zbl 0845.05085) Full Text: DOI