Accession Number : AD1003124


Title :   A Comparison of Approaches for Solving Hard Graph-Theoretic Problems


Descriptive Note : Journal Article


Corporate Author : Air Force Research Laboratory/RITF ROME United States


Personal Author(s) : Horan,Victoria ; Adachi,Steve ; Bak,Stanley


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/1003124.pdf


Report Date : 29 Apr 2015


Pagination or Media Count : 24


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


Descriptors :   COMPUTATIONAL SCIENCE , Parallel Computing , graphs


Distribution Statement : APPROVED FOR PUBLIC RELEASE