The subgraph homeomorphism problem

Andrea S. Lapaugh; Ronald L. Rivest

doi:10.1016/0022-0000(80)90057-4

The subgraph homeomorphism problem

Andrea S. Lapaugh, Ronald L. Rivest

Computer Science

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

Abstract

We investigate the problem of finding a homeomorphic image of a "pattern" graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G (here H is a triangle). No polynomial time algorithm for this problem was previously known. We also discuss a variety of reductions between related versions of this problem and a number of open problems.

Original language	English (US)
Pages (from-to)	133-149
Number of pages	17
Journal	Journal of Computer and System Sciences
Volume	20
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(80)90057-4
State	Published - Apr 1980

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/0022-0000(80)90057-4

Cite this

@article{d3ce5d5f5ccc4219854615de0783179a,

title = "The subgraph homeomorphism problem",

abstract = "We investigate the problem of finding a homeomorphic image of a {"}pattern{"} graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G (here H is a triangle). No polynomial time algorithm for this problem was previously known. We also discuss a variety of reductions between related versions of this problem and a number of open problems.",

author = "Lapaugh, {Andrea S.} and Rivest, {Ronald L.}",

year = "1980",

month = apr,

doi = "10.1016/0022-0000(80)90057-4",

language = "English (US)",

volume = "20",

pages = "133--149",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - The subgraph homeomorphism problem

AU - Lapaugh, Andrea S.

AU - Rivest, Ronald L.

PY - 1980/4

Y1 - 1980/4

N2 - We investigate the problem of finding a homeomorphic image of a "pattern" graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G (here H is a triangle). No polynomial time algorithm for this problem was previously known. We also discuss a variety of reductions between related versions of this problem and a number of open problems.

AB - We investigate the problem of finding a homeomorphic image of a "pattern" graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G (here H is a triangle). No polynomial time algorithm for this problem was previously known. We also discuss a variety of reductions between related versions of this problem and a number of open problems.

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

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

U2 - 10.1016/0022-0000(80)90057-4

DO - 10.1016/0022-0000(80)90057-4

M3 - Article

AN - SCOPUS:0019004114

SN - 0022-0000

VL - 20

SP - 133

EP - 149

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

The subgraph homeomorphism problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this