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