TY - GEN

T1 - Parallel algorithms for the subgraph homeomorphism problem

AU - Khuller, Samir

N1 - Funding Information:
*supported by NSF grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs.
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 -