Subgraph Isomorphism

GPTKB entity

Statements (26)
Predicate Object
gptkbp:instanceOf Computational Problem
gptkbp:application gptkb:Computer_Vision
gptkb:Bioinformatics
gptkb:Pattern_Recognition
Chemistry
gptkbp:category gptkb:Decision_Problem
Graph Problem
gptkbp:complexity NP-complete
gptkbp:defines Given two graphs G and H, determine whether G contains a subgraph that is isomorphic to H.
gptkbp:field gptkb:Graph_Theory
Computer Science
gptkbp:firstDescribed 1970s
gptkbp:generalizes Hamiltonian Cycle Problem
Clique Problem
Graph Isomorphism Problem
gptkbp:hardness gptkb:NP-hard
https://www.w3.org/2000/01/rdf-schema#label Subgraph Isomorphism
gptkbp:input Two graphs G and H
gptkbp:output Boolean (True if G contains a subgraph isomorphic to H, False otherwise)
gptkbp:relatedTo gptkb:Graph_Isomorphism
Subgraph
gptkbp:solvedBy RI Algorithm
Ullmann's Algorithm
VF2 Algorithm
gptkbp:bfsParent gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
gptkbp:bfsLayer 6