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

Samir Khuller*, Stephen G. Mitchell, Vijay V. Vazirani

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages300-305
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Conference

Conference30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph'. Together they form a unique fingerprint.

  • Cite this

    Khuller, S., Mitchell, S. G., & Vazirani, V. V. (1989). Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 300-305). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1989.63494