EUVIMEDEUVIMED entdecken
Crossref

Error-correcting open-locating-dominating sets

Devin C. Jean, Suk J. Seo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →