Premium
Recognizing small subgraphs
Author(s) -
Sundaram Gopalakrishnan,
Skiena Steven S.
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230250404
Subject(s) - subgraph isomorphism problem , induced subgraph isomorphism problem , combinatorics , mathematics , graph isomorphism , time complexity , isomorphism (crystallography) , graph , induced subgraph , vertex connectivity , discrete mathematics , graph factorization , computer science , line graph , graph power , vertex (graph theory) , voltage graph , chemistry , crystal structure , crystallography
Although the general problem of subgraph isomorphism is NP‐complete, polynomial‐time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. In this paper, we present general algorithms for fixed‐subgraph isomorphism which improve or unify previous results. In particular, we present an O(n f m) algorithm for recognizing a fixed subgraph H with flower number f within a graph G with n vertices and m edges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizing C 5 and small even cycles C 2k , k ≥ 3.