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 di cult 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. 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2015
- Accession Number
- ADA623530
Entities
People
- Stanley Bak
- Steve Adachi
- Victoria Horan
Organizations
- Air Force Research Laboratory