subgraph isomorphism problem
GPTKB entity
Statements (25)
Predicate | Object |
---|---|
gptkbp:instanceOf |
theoretical computer science
|
gptkbp:application |
chemistry
computer vision network analysis pattern recognition |
gptkbp:category |
theoretical computer science
|
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 |
computer science
graph theory |
gptkbp:generalizes |
gptkb:Hamiltonian_cycle_problem
gptkb:clique_problem gptkb:independent_set_problem |
gptkbp:hardness |
gptkb:NP-hard
|
gptkbp:hasWikipediaPage |
https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
|
https://www.w3.org/2000/01/rdf-schema#label |
subgraph isomorphism problem
|
gptkbp:introducedIn |
1970s
|
gptkbp:relatedTo |
gptkb:graph_isomorphism_problem
gptkb:clique_problem |
gptkbp:solvedBy |
gptkb:Ullmann's_algorithm
gptkb:VF2_algorithm RI algorithm |
gptkbp:bfsParent |
gptkb:graph_isomorphism_problem
gptkb:Clique_problem |
gptkbp:bfsLayer |
6
|