Optimal Error-detection system for Identifying Codes
From MaRDI portal
Publication:6407657
arXiv2208.06052MaRDI QIDQ6407657FDOQ6407657
Publication date: 11 August 2022
Abstract: Assume that a graph models a detection system for a facility with a possible ``intruder," or a multiprocessor network with a possible malfunctioning processor. We consider the problem of placing detectors at a subset of vertices in to determine the location of an intruder if there is any. Many types of detection systems have been defined for different sensor capabilities; in particular, we focus on Identifying Codes, where each detector can determine whether there is an intruder within its closed neighborhood. In this research we explore a fault-tolerant variant of identifying codes applicable to real-world systems. Specifically, error-detecting identifying codes permit a false negative transmission from any single detector. We investigate minimum-sized error-detecting identifying codes in several classes of graphs, including cubic graphs and infinite grids, and show that the problem of determining said minimum size in arbitrary graphs is NP-complete.
This page was built for publication: Optimal Error-detection system for Identifying Codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407657)
