| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141637 | Discrete Optimization | 2013 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
M.P. Dobson, V. Leoni, G. Nasini,