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