| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6875826 | Theoretical Computer Science | 2017 | 16 Pages |
Abstract
We present and compare various methods to construct efficient QUBO formulations for the Graph Isomorphism Problem-one of a very few problems in NP that is neither known to be solvable in polynomial time nor NP-complete-and two related Subgraph Isomorphism Problems that are NP-hard. Experimental results on two QUBO formulations of the Graph Isomorphism Problem suggest that our direct formulation is more practical than the others with respect to running on the D-Wave architecture.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Cristian S. Calude, Michael J. Dinneen, Richard Hua,