@Article{LPR80,
author = { Andrea S. LaPaugh and Ronald L. Rivest },
title = { The Subgraph homeomorphism problem },
journal = { JCSS },
OPTyear = { 1980 },
OPTmonth = { April },
date = { 1980-04 },
volume = { 20 },
number = { 2 },
pages = { 133--149 },
issn = { 0022-0000 },
doi = { 10.1016/0022-0000(80)90057-4 },
url = { http://www.sciencedirect.com/science/article/pii/0022000080900574 },
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.
},
}