Ronald Fagin
Journal of the ACM
Given an undirected graph G = (V, E) and vertices s,,tt; s2,t2, the problem is to determine whether or not G admits two vertex disjoint paths P, and P2 connecting s, with t, and s2 with t2, respectively. This problem is solved by an O(n.m) algorithm (n = IVJ, m = JElL An important by-product of the paper is a theorem stating that if G is 4-connected and nonplanar, then such paths P, and P2 exist for any choice of s,, s2, h, and t2 (as conjectured by Watkins). © 1980, ACM. All rights reserved.
Ronald Fagin
Journal of the ACM
Annina Riedhauser, Viacheslav Snigirev, et al.
CLEO 2023
Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
Ryan Johnson, Ippokratis Pandis
CIDR 2013