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

Report Date:

2015-04-29

Pagination or Media Count:

24.0

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

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE