We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A comparison of approaches for finding minimum identifying codes on graphs.
- Authors
Horan, Victoria; Adachi, Steve; Bak, Stanley
- Abstract
In order to formulate mathematical conjectures likely to be true, a number of base cases must be determined. However, many combinatorial problems are NP-hard and the computational complexity makes this research approach difficult using a standard brute force approach on a typical computer. One sample problem explored is that of finding a minimum identifying code. To work around the computational issues, a variety of methods are explored and consist of a parallel computing approach using MATLAB, an adiabatic quantum optimization approach using a D-Wave quantum annealing processor, and lastly using satisfiability modulo theory (SMT) and corresponding SMT solvers. Each of these methods requires the problem to be formulated in a unique manner. In this paper, we address the challenges of computing solutions to this NP-hard problem with respect to each of these methods.
- Subjects
QUANTUM graph theory; COMBINATORICS; COMPUTATIONAL complexity; SATISFIABILITY (Computer science); QUANTUM computing
- Publication
Quantum Information Processing, 2016, Vol 15, Issue 5, p1827
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-016-1240-0