Artículo

A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games

Dobson, Maria Patricia; Leoni, Valeria AlejandraIcon ; Nasini, Graciela LeonorIcon
Fecha de publicación: 02/2013
Editorial: Elsevier Science
Revista: Discrete Optimization
ISSN: 1572-5286
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

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.
Palabras clave: Edge-Perfect , Graph , Np-Completeness , Totally Balanced Game
 
Archivos asociados
Thumbnail
 
Tamaño: 289.7Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/79345
DOI: http://dx.doi.org/10.1016/j.disopt.2012.10.004
URL: https://www.sciencedirect.com/science/article/pii/S1572528612000722
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Citación
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
Compartir
Altmétricas