Error-correcting open-locating-dominating sets
Congressus Numerantium · 2025
DOI: 10.61091/cn235-03 ↗Kurz gefasst
Fachartikel in der Zeitschrift Congressus Numerantium, 2025. Verfasst von Devin C. Jean und 1 weiteren Autor:innen.
Abstract (Originalsprache)
An open-locating-dominating set of a graph models a detection system for a facility with a possible “intruder” or a multiprocessor network with a possible malfunctioning processor. A “sensor” or “detector” is assumed to be installed at a subset of vertices where each can detect an intruder or a malfunctioning processor in its neighborhood, but not at its own location. We consider a fault-tolerant variant of an open-locating-dominating set called an error-correcting open-locating-dominating set, which can correct a false-positive or a false-negative signal from a detector. In particular, we prove the problem of finding a minimum error-correcting open-locating-dominating set in an arbitrary graph is NP-complete. Additionally, we characterize the existence criteria for an error-correcting open-locating-dominating set in an arbitrary graph. We also consider extremal graphs that require every vertex to be a detector and minimum error-correcting open-locating-dominating sets in infinite grids.
Zitieren
APA
Jean, D. C., & Seo, S. J. (2025). Error-correcting open-locating-dominating sets. Congressus Numerantium. https://doi.org/10.61091/cn235-03
Vancouver
Jean DC, Seo SJ. Error-correcting open-locating-dominating sets. Congressus Numerantium. 2025. doi:10.61091/cn235-03
BibTeX
@article{Jean2025,
author = {Jean, Devin C. and Seo, Suk J.},
title = {Error-correcting open-locating-dominating sets},
journal = {Congressus Numerantium},
year = {2025},
doi = {10.61091/cn235-03}
}
EUVIMED