Mostrar el registro sencillo del ítem
dc.contributor.author
Dobson, Maria Patricia
dc.contributor.author
Leoni, Valeria Alejandra
dc.contributor.author
Nasini, Graciela Leonor
dc.date.available
2019-07-11T15:31:54Z
dc.date.issued
2013-02
dc.identifier.citation
Dobson, Maria Patricia; Leoni, Valeria Alejandra; Nasini, Graciela Leonor; A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games; Elsevier Science; Discrete Optimization; 10; 1; 2-2013; 54-60
dc.identifier.issn
1572-5286
dc.identifier.uri
http://hdl.handle.net/11336/79345
dc.description.abstract
We characterize edge-perfect graphs and prove that it is co-NP-complete to recognize them. In consequence, recognizing the defining matrices of totally balanced packing games is also co-NP-complete, in contrast with the polynomiality for the covering case. In addition, we solve the computational complexity of universally balanced (with respect to the resources constraints) packing games.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Edge-Perfect
dc.subject
Graph
dc.subject
Np-Completeness
dc.subject
Totally Balanced Game
dc.subject.classification
Matemática Pura
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games
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-06-19T12:21:10Z
dc.journal.volume
10
dc.journal.number
1
dc.journal.pagination
54-60
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Dobson, Maria Patricia. 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: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; 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: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; 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.journal.title
Discrete Optimization
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.disopt.2012.10.004
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1572528612000722
Archivos asociados
Tamaño:
289.7Kb
Formato:
PDF