×

A linear algorithm for the two paths problem on permutation graphs. (English) Zbl 0845.05085

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
PDFBibTeX XMLCite
Full Text: DOI