### 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 - Jan 1 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

- 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, .