The subgraph homeomorphism problem

Andrea S. La Paugh; Ronald L. Rivest

doi:10.1145/800133.804330

The subgraph homeomorphism problem

Andrea S. La Paugh
, Ronald L. Rivest

Computer Science

Research output: Contribution to journal › Conference article › peer-review

2 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)	40-50
Number of pages	11
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800133.804330
State	Published - May 1 1978
Event	10th Annual ACM Symposium on Theory of Computing, STOC 1978 - San Diego, United States Duration: May 1 1978 → May 3 1978

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800133.804330

Cite this

@article{50788c55c25745ab9332110caa651174,

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 = "\{La Paugh\}, \{Andrea S.\} and Rivest, \{Ronald L.\}",

note = "Publisher Copyright: {\textcopyright} 1978 Association for Computing Machinery. All rights reserved.; 10th Annual ACM Symposium on Theory of Computing, STOC 1978 ; Conference date: 01-05-1978 Through 03-05-1978",

year = "1978",

month = may,

day = "1",

doi = "10.1145/800133.804330",

language = "English (US)",

pages = "40--50",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - The subgraph homeomorphism problem

AU - La Paugh, Andrea S.

AU - Rivest, Ronald L.

PY - 1978/5/1

Y1 - 1978/5/1

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 - https://www.scopus.com/pages/publications/85053057374

UR - https://www.scopus.com/pages/publications/85053057374#tab=citedBy

U2 - 10.1145/800133.804330

DO - 10.1145/800133.804330

M3 - Conference article

AN - SCOPUS:85053057374

SN - 0737-8017

SP - 40

EP - 50

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 10th Annual ACM Symposium on Theory of Computing, STOC 1978

Y2 - 1 May 1978 through 3 May 1978

ER -

The subgraph homeomorphism problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this