Parallel algorithms for the subgraph homeomorphism problem

Samir Khuller*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference 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 K4 or K2,3, if it is not.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - Workshop, WADS 1989, Proceedings
EditorsFrank Dehne, Jorg-Rudige Sack, Nicola Santoro
PublisherSpringer Verlag
Pages303-315
Number of pages13
ISBN (Print)9783540515425
DOIs
StatePublished - 1989
EventWorkshop on Algorithms and Data Structures, WADS 1989 - Ottawa, Canada
Duration: Aug 17 1989Aug 19 1989

Publication series

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

Conference

ConferenceWorkshop on Algorithms and Data Structures, WADS 1989
CountryCanada
CityOttawa
Period8/17/898/19/89

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parallel algorithms for the subgraph homeomorphism problem'. Together they form a unique fingerprint.

Cite this