Reductions between the Subgraph Isomorphism Problem and Hamiltonian and SAT Problems.
Iván OlmosJesús A. GonzálezMauricio OsorioPublished in: CONIELECOMP (2007)
Keyphrases
- subgraph isomorphism
- sat problem
- sat solvers
- satisfiability problem
- search tree
- graph matching
- phase transition
- constraint satisfaction problems
- np complete
- randomly generated
- edit distance
- hard problems
- sat instances
- graph databases
- weighted graph
- graph mining
- decision problems
- constraint satisfaction
- temporal logic
- graph patterns
- orders of magnitude
- depth first search
- branch and bound
- machine learning
- lower bound