The subgraph homeomorphism problem

Andrea S. Lapaugh, Ronald L. Rivest

Research output: Contribution to journalArticle

39 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)133-149
Number of pages17
JournalJournal of Computer and System Sciences
Volume20
Issue number2
DOIs
StatePublished - Apr 1980

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The subgraph homeomorphism problem'. Together they form a unique fingerprint.

  • Cite this