@InProceedings{LPR78,
replaced-by = { LPR80 },
author = { Andrea S. LaPaugh and Ronald L. Rivest },
title = { The subgraph homeomorphism problem },
pages = { 40--50 },
url = { http://doi.acm.org/10.1145/800133.804330 },
doi = { 10.1145/800133.804330 },
acmid = { 804330 },
acm = { 08117 },
booktitle = { Proceedings of the tenth annual ACM symposium on Theory of computing },
date = { 1978 },
publisher = { ACM },
editor = { Richard J. Lipton },
OPTyear = { 1978 },
OPTmonth = { May 1--3, },
eventdate = { 1978-05-01/1978-05-03 },
eventtitle = { STOC '78 },
venue = { San Diego, California },
OPTorganization = { ACM },
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.
},
}