INVESTIGADORES
LEONI Valeria Alejandra
artículos
Título:
A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games
Autor/es:
DOBSON, M.P; LEONI, V.; NASINI, G.
Revista:
DISCRETE OPTIMIZATION
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2013 vol. 10 p. 54 - 60
ISSN:
1572-5286
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.
