Journal
DISCRETE OPTIMIZATION
Volume 10, Issue 1, Pages 54-60Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disopt.2012.10.004
Keywords
Edge-perfect; Graph; Totally balanced game; NP-completeness
Ask authors/readers for more resources
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. (C) 2012 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
