Parallel algorithms for the subgraph homeomorphism problem

Samir Khuller

doi:10.1007/3-540-51542-9_26

Parallel algorithms for the subgraph homeomorphism problem

Samir Khuller^*

^*Corresponding author for this work

Computer Science

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

Abstract

The subgraph homeomorphism problem for a fixed graph H is stated as follows: given a graph G, determine whether G has a subgraph homeomorphic to H, and obtain it. We study the parallel complexity of this problem for various pattern graphs H, and present fast NC algorithms for various versions of this problem. We also present an efficient NC algorithm to check if a given graph is outer-planar and to obtain its forbidden homeomorphs K₄ or K_2,3, if it is not.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - Workshop, WADS 1989, Proceedings
Editors	Frank Dehne, Jorg-Rudige Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	303-315
Number of pages	13
ISBN (Print)	9783540515425
DOIs	https://doi.org/10.1007/3-540-51542-9_26
State	Published - 1989
Event	Workshop on Algorithms and Data Structures, WADS 1989 - Ottawa, Canada Duration: Aug 17 1989 → Aug 19 1989

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	382 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Workshop on Algorithms and Data Structures, WADS 1989
Country/Territory	Canada
City	Ottawa
Period	8/17/89 → 8/19/89

Funding

*supported by NSF grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-51542-9_26

Cite this

Khuller, S. (1989). Parallel algorithms for the subgraph homeomorphism problem. In F. Dehne, J.-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - Workshop, WADS 1989, Proceedings (pp. 303-315). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 382 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-51542-9_26

Khuller, Samir. / Parallel algorithms for the subgraph homeomorphism problem. Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. editor / Frank Dehne ; Jorg-Rudige Sack ; Nicola Santoro. Springer Verlag, 1989. pp. 303-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c137bbb3acfe4953897d15ffe9ce3e68,

title = "Parallel algorithms for the subgraph homeomorphism problem",

abstract = "The subgraph homeomorphism problem for a fixed graph H is stated as follows: given a graph G, determine whether G has a subgraph homeomorphic to H, and obtain it. We study the parallel complexity of this problem for various pattern graphs H, and present fast NC algorithms for various versions of this problem. We also present an efficient NC algorithm to check if a given graph is outer-planar and to obtain its forbidden homeomorphs K4 or K2,3, if it is not.",

author = "Samir Khuller",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1989.; Workshop on Algorithms and Data Structures, WADS 1989 ; Conference date: 17-08-1989 Through 19-08-1989",

year = "1989",

doi = "10.1007/3-540-51542-9_26",

language = "English (US)",

isbn = "9783540515425",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "303--315",

editor = "Frank Dehne and Jorg-Rudige Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - Workshop, WADS 1989, Proceedings",

}

Khuller, S 1989, Parallel algorithms for the subgraph homeomorphism problem. in F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 382 LNCS, Springer Verlag, pp. 303-315, Workshop on Algorithms and Data Structures, WADS 1989, Ottawa, Canada, 8/17/89. https://doi.org/10.1007/3-540-51542-9_26

Parallel algorithms for the subgraph homeomorphism problem. / Khuller, Samir.
Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. ed. / Frank Dehne; Jorg-Rudige Sack; Nicola Santoro. Springer Verlag, 1989. p. 303-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 382 LNCS).

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

TY - GEN

T1 - Parallel algorithms for the subgraph homeomorphism problem

AU - Khuller, Samir

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1989.

PY - 1989

Y1 - 1989

N2 - The subgraph homeomorphism problem for a fixed graph H is stated as follows: given a graph G, determine whether G has a subgraph homeomorphic to H, and obtain it. We study the parallel complexity of this problem for various pattern graphs H, and present fast NC algorithms for various versions of this problem. We also present an efficient NC algorithm to check if a given graph is outer-planar and to obtain its forbidden homeomorphs K4 or K2,3, if it is not.

AB - The subgraph homeomorphism problem for a fixed graph H is stated as follows: given a graph G, determine whether G has a subgraph homeomorphic to H, and obtain it. We study the parallel complexity of this problem for various pattern graphs H, and present fast NC algorithms for various versions of this problem. We also present an efficient NC algorithm to check if a given graph is outer-planar and to obtain its forbidden homeomorphs K4 or K2,3, if it is not.

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

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

U2 - 10.1007/3-540-51542-9_26

DO - 10.1007/3-540-51542-9_26

M3 - Conference contribution

AN - SCOPUS:85031915326

SN - 9783540515425

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 303

EP - 315

BT - Algorithms and Data Structures - Workshop, WADS 1989, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudige

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - Workshop on Algorithms and Data Structures, WADS 1989

Y2 - 17 August 1989 through 19 August 1989

ER -

Khuller S. Parallel algorithms for the subgraph homeomorphism problem. In Dehne F, Sack JR, Santoro N, editors, Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. Springer Verlag. 1989. p. 303-315. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-51542-9_26

Parallel algorithms for the subgraph homeomorphism problem

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this