Polyhedra associated with identifying codes in graphs

Autor: Annegret Wagler, Gabriela R. Argiroffo, Silvia M. Bianchi, Yanina Lucarini
Přispěvatelé: Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Université de Neuchâtel (UNINE), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Wagler, Annegret
Jazyk: angličtina
Rok vydání: 2018
Předmět:
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]
Matemáticas
ODD HYPERCYCLES
0211 other engineering and technologies
Structure (category theory)
IDENTIFYING CODE CLUTTER
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
identifying code polyhedron
IDENTIFYING CODE POLYHEDRON
Combinatorics
Polyhedron
odd hypercycles
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Code (cryptography)
Discrete Mathematics and Combinatorics
Order (group theory)
Search problem
Point (geometry)
Otras Matemáticas
[INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM]
Mathematics
Discrete mathematics
021103 operations research
Applied Mathematics
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
identifying code clutter
010201 computation theory & mathematics
Line (geometry)
Bipartite graph
[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]
CIENCIAS NATURALES Y EXACTAS
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Discrete Applied Mathematics
Discrete Applied Mathematics, 2018, 245, pp.16-27. ⟨10.1016/j.dam.2017.06.005⟩
Discrete Applied Mathematics, Elsevier, 2018, 245, pp.16-27
Discrete Applied Mathematics, Elsevier, 2018, 245, pp.16-27. ⟨10.1016/j.dam.2017.06.005⟩
Discrete Applied Mathematics, 2018, 245, pp.16-27
ISSN: 0166-218X
Popis: The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size. In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for special graphs, and discuss further lines of research in order to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Bianchi, Silvia María. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Lucarini, Yanina Paola. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Wagler, Annegret Katrin. Université Clermont Auvergne; Francia
Databáze: OpenAIRE
Externí odkaz: