A comparison of approaches for finding minimum identifying codes on graphs

DOI10.1007/S11128-016-1240-0MaRDI QIDQ296102zbMATH OpenOpenAlexFDO

Authors Victoria Horan, Steve Adachi, Stanley Bak

Publication date 14 June 2016

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.08011

zbMATH Keywords

graph theoryquantum annealingSMT solvers

Mathematics Subject Classification ID

Quantum computation (81P68)

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. 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.

Recommendations

• Minimum identifying codes in some graphs differing by matchings
• The minimum identifying code graphs
• Minimum sizes of identifying codes in graphs differing by one vertex
• Minimum sizes of identifying codes in graphs differing by one edge
• On a new class of identifying codes in graphs
• On the minimum size of an identifying code over all orientations of a graph
• Extremal graphs for the identifying code problem
• On minimum identifying codes in some Cartesian product graphs
• On a new class of codes for identifying vertices in graphs
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm

Cites work

• scientific article; zbMATH DE number 3167699 (Why is no real title available?)
• A case study in programming a quantum annealer for hard operational planning problems
• Adiabatic quantum programming: minor embedding with hard faults
• Identifying codes on directed de Bruijn graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• On a new class of codes for identifying vertices in graphs
• Resource efficient gadgets for compiling adiabatic quantum optimization problems

Cited in

(2)

• An optimal lower bound on the number of variables for graph identification
• Watching systems in graphs: an extension of identifying codes

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: A comparison of approaches for finding minimum identifying codes on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q296102)