The subgraph homeomorphism problem
作者:
Highlights:
•
摘要
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.
论文关键词:
论文评审过程:Received 10 October 1979, Available online 2 December 2003.
论文官网地址:https://doi.org/10.1016/0022-0000(80)90057-4