TY - GEN

T1 - Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph

AU - Khuller, Samir

AU - Mitchell, Stephen G.

AU - Vazirani, Vijay V.

PY - 1989

Y1 - 1989

N2 - Given a graph G and two pairs of vertices s1, t1 and s2, t2, the two disjoint paths problem asks for vertex-disjoint paths connecting si with ti, i = 1, 2. A fast parallel (NC) algorithm is given for this problem, which has applications in certain routing situations. If G is nonplanar, an algorithm that finds a Kuratowski homeomorph in G (i.e., a subgraph homeomorphic to K3,3 or K5) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm here provides a certificate of nonplanarity in the negative case. Both algorithms are processor efficient; in each case, the processor-time product is within a polylogarithmic factor of the best known sequential algorithm.

AB - Given a graph G and two pairs of vertices s1, t1 and s2, t2, the two disjoint paths problem asks for vertex-disjoint paths connecting si with ti, i = 1, 2. A fast parallel (NC) algorithm is given for this problem, which has applications in certain routing situations. If G is nonplanar, an algorithm that finds a Kuratowski homeomorph in G (i.e., a subgraph homeomorphic to K3,3 or K5) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm here provides a certificate of nonplanarity in the negative case. Both algorithms are processor efficient; in each case, the processor-time product is within a polylogarithmic factor of the best known sequential algorithm.

UR - http://www.scopus.com/inward/record.url?scp=0024765830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024765830&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1989.63494

DO - 10.1109/sfcs.1989.63494

M3 - Conference contribution

AN - SCOPUS:0024765830

SN - 0818619821

SN - 9780818619823

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 300

EP - 305

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

T2 - 30th Annual Symposium on Foundations of Computer Science

Y2 - 30 October 1989 through 1 November 1989

ER -