Polyhedra associated with identifying codes in graphs | ||
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Université Clermont Auvergne | |
| dc.contributor.author | Argiroffo, Gabriela Rut | |
| dc.contributor.author | Bianchi, Silvia María | |
| dc.contributor.author | Lucarini, Yanina Paola | |
| dc.contributor.author | Wagler, Annegret Katrin | |
| dc.date.issued | 2018-08 | |
| dc.description.abstract | 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. | es |
| dc.description.fil | 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 | |
| dc.description.fil | 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 | |
| dc.description.fil | 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 | |
| dc.description.fil | Fil: Wagler, Annegret Katrin. Université Clermont Auvergne; Francia | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Argiroffo, Gabriela Rut; Bianchi, Silvia María; Lucarini, Yanina Paola; Wagler, Annegret Katrin; Polyhedra associated with identifying codes in graphs; Elsevier Science; Discrete Applied Mathematics; 245; 8-2018; 16-27 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/100790 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 16-27 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 245 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0166218X17302913 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.dam.2017.06.005 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | IDENTIFYING CODE POLYHEDRON | es |
| dc.subject | IDENTIFYING CODE CLUTTER | es |
| dc.subject | ODD HYPERCYCLES | es |
| dc.subject.classification | Otras Matemáticas | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Polyhedra associated with identifying codes in graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.839ff168-7768-4fc3-9aa3-5442b9d1f358_A.pdf
- Tamaño:
- 363.98 KB
- Formato:
- Adobe Portable Document Format