SUBGRAPH HOMEOMORPHISM PROBLEM.

Andrea S. LaPaugh; Ronald L. Rivest

SUBGRAPH HOMEOMORPHISM PROBLEM.

Andrea S. LaPaugh
, Ronald L. Rivest

Computer Science

Research output: Contribution to conference › Paper › peer-review

36 Scopus citations

Abstract

The problem of finding a homeomorphic image of a ″pattern″ graph H in a larger input graph G is investigated. This problem is viewed as finding specified sets of edge disjoint or node disjoint paths in G. The 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. A variety of reductions between related versions of this problem and a number of open problems is also discussed.

Original language	English (US)
Pages	40-50
Number of pages	11
State	Published - 1978
Event	Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA Duration: May 1 1978 → May 3 1978

Other

Other	Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp
City	San Diego, CA, USA
Period	5/1/78 → 5/3/78

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@conference{4c9b75b95b0b45809c98c6f21ad52b04,

title = "SUBGRAPH HOMEOMORPHISM PROBLEM.",

abstract = "The problem of finding a homeomorphic image of a ″pattern″ graph H in a larger input graph G is investigated. This problem is viewed as finding specified sets of edge disjoint or node disjoint paths in G. The 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. A variety of reductions between related versions of this problem and a number of open problems is also discussed.",

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

year = "1978",

language = "English (US)",

pages = "40--50",

note = "Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp ; Conference date: 01-05-1978 Through 03-05-1978",

}

TY - CONF

T1 - SUBGRAPH HOMEOMORPHISM PROBLEM.

AU - LaPaugh, Andrea S.

AU - Rivest, Ronald L.

PY - 1978

Y1 - 1978

N2 - The problem of finding a homeomorphic image of a ″pattern″ graph H in a larger input graph G is investigated. This problem is viewed as finding specified sets of edge disjoint or node disjoint paths in G. The 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. A variety of reductions between related versions of this problem and a number of open problems is also discussed.

AB - The problem of finding a homeomorphic image of a ″pattern″ graph H in a larger input graph G is investigated. This problem is viewed as finding specified sets of edge disjoint or node disjoint paths in G. The 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. A variety of reductions between related versions of this problem and a number of open problems is also discussed.

UR - https://www.scopus.com/pages/publications/0018058201

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

M3 - Paper

AN - SCOPUS:0018058201

SP - 40

EP - 50

T2 - Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp

Y2 - 1 May 1978 through 3 May 1978

ER -

SUBGRAPH HOMEOMORPHISM PROBLEM.

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this