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

Samir Khuller; Stephen G. Mitchell; Vijay V. Vazirani

doi:10.1109/sfcs.1989.63494

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

Given a graph G and two pairs of vertices s₁, t₁ and s₂, t₂, the two disjoint paths problem asks for vertex-disjoint paths connecting s_i with t_i, 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 K_3,3 or K₅) 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 language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	Publ by IEEE
Pages	300-305
Number of pages	6
ISBN (Print)	0818619821, 9780818619823
DOIs	https://doi.org/10.1109/sfcs.1989.63494
State	Published - 1989
Event	30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA Duration: Oct 30 1989 → Nov 1 1989

Publication series

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

Conference

Conference	30th Annual Symposium on Foundations of Computer Science
City	Research Triangle Park, NC, USA
Period	10/30/89 → 11/1/89

ASJC Scopus subject areas

Hardware and Architecture

Access to Document

10.1109/sfcs.1989.63494

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

@inproceedings{4c5d2c787a584f06ad36ea1297cecb86,

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

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.",

author = "Samir Khuller and Mitchell, {Stephen G.} and Vazirani, {Vijay V.}",

year = "1989",

doi = "10.1109/sfcs.1989.63494",

language = "English (US)",

isbn = "0818619821",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "Publ by IEEE",

pages = "300--305",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

note = "30th Annual Symposium on Foundations of Computer Science ; Conference date: 30-10-1989 Through 01-11-1989",

}

Khuller, S, Mitchell, SG & Vazirani, VV 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). Annual Symposium on Foundations of Computer Science (Proceedings), Publ by IEEE, pp. 300-305, 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA, 10/30/89. https://doi.org/10.1109/sfcs.1989.63494

Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph. / Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, 1989. p. 300-305 (Annual Symposium on Foundations of Computer Science (Proceedings)).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this