Mostrar el registro sencillo del ítem
dc.contributor.author
Argiroffo, Gabriela Rut
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Bianchi, Silvia María
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Lucarini, Yanina Paola
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Wagler, Annegret Katrin
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2019-09-24T22:15:22Z
dc.date.issued
2017-11
dc.identifier.citation
Argiroffo, Gabriela Rut; Bianchi, Silvia María; Lucarini, Yanina Paola; Wagler, Annegret Katrin; A linear-time algorithm for the identifying code problem on block graphs; Elsevier Science; Electronic Notes in Discrete Mathematics; 62; 11-2017; 249-254
dc.identifier.issn
1571-0653
dc.identifier.uri
http://hdl.handle.net/11336/84375
dc.description.abstract
The identifying code problem is a special search problem, challenging both from a theoretical and from a computational point of view, even for several graphs where other usually hard problems are easy to solve, like bipartite graphs or chordal graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs. In this work we study the problem of determining the cardinality of a minimum identifying code in block graphs (that are diamond-free chordal graphs). We present a linear-time algorithm for this problem, as a generalization of a linear-time algorithm proposed by Auger in 2010 for the case of trees. Thereby, we provide a subclass of chordal graphs for which the identifying code problem can be solved in linear time.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Block Graphs
dc.subject
Computational Complexity
dc.subject
Identifying Codes
dc.subject.classification
Otras Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
A linear-time algorithm for the identifying code problem on block graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-09-23T17:10:24Z
dc.journal.volume
62
dc.journal.pagination
249-254
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Argiroffo, Gabriela Rut. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. 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. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. 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: Wagler, Annegret Katrin. University Clermont Auvergne; Francia
dc.journal.title
Electronic Notes in Discrete Mathematics
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065317302822
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.endm.2017.10.043
Archivos asociados