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 :

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