A comparison of approaches for finding minimum identifying codes on graphs
From MaRDI portal
Publication:296102
DOI10.1007/S11128-016-1240-0zbMATH Open1338.81136arXiv1504.08011OpenAlexW2329390440MaRDI QIDQ296102FDOQ296102
Victoria Horan, Steve Adachi, Stanley Bak
Publication date: 14 June 2016
Published in: Quantum Information Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1504.08011
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
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Adiabatic quantum programming: minor embedding with hard faults
- Title not available (Why is that?)
- On a new class of codes for identifying vertices in graphs
- Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
- A case study in programming a quantum annealer for hard operational planning problems
- Identifying codes on directed de Bruijn graphs
- Resource efficient gadgets for compiling adiabatic quantum optimization problems
Cited In (2)
Uses Software
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)
