A Comparison of Approaches for Solving Hard Graph-Theoretic Problems
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, a quantum annealing approach using the D-Wave computer, and lastly using satisfiability modulo theory (SMT) and corresponding SMT solvers
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 29, 2015
- Accession Number
- AD1003124
Entities
People
- Stanley Bak
- Steve Adachi
- Victoria Horan