SUBGRAPH HOMEOMORPHISM PROBLEM.

Andrea Suzanne LaPaugh, Ronald L. Rivest

Research output: Contribution to conferencePaper

31 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 languageEnglish (US)
Pages40-50
Number of pages11
StatePublished - Jan 1 1978
EventConf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA
Duration: May 1 1978May 3 1978

Other

OtherConf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp
CitySan Diego, CA, USA
Period5/1/785/3/78

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'SUBGRAPH HOMEOMORPHISM PROBLEM.'. Together they form a unique fingerprint.

  • Cite this

    LaPaugh, A. S., & Rivest, R. L. (1978). SUBGRAPH HOMEOMORPHISM PROBLEM.. 40-50. Paper presented at Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp, San Diego, CA, USA, .