Watching systems in graphs: An extension of identifying codes

Autor: Olivier Hudry, Irène Charon, Antoine Lobstein, David Auger
Přispěvatelé: MAGMAT, Laboratoire Traitement et Communication de l'Information (LTCI), Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Télécom ParisTech, Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2013
Předmět:
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Generalization
Computer Science::Human-Computer Interaction
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Upper and lower bounds
Identifying codes
Computer Science::Multimedia
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Mathematics
Discrete mathematics
Applied Mathematics
Paths
020206 networking & telecommunications
Graph theory
Complexity
Extension (predicate logic)
16. Peace & justice
010201 computation theory & mathematics
Cycles
Combinatorics (math.CO)
Watching systems
Computer Science - Discrete Mathematics
Zdroj: Discrete Applied Mathematics. 161:1674-1685
ISSN: 0166-218X
Popis: We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.
Databáze: OpenAIRE
Externí odkaz: