Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420848 | Discrete Applied Mathematics | 2008 | 7 Pages |
Abstract
We define a new set of functions called semi-monotone, a subclass of skew-supermodular functions. We show that the problem of augmenting a given graph to cover a symmetric semi-monotone function is NP-complete if all the values of the function are in {0,1}{0,1} and we provide a minimax theorem if all the values of the function are different from 1. Our problem is equivalent to the node to area augmentation problem. Our contribution is to provide a significantly simpler and shorter proof.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Roland Grappe, Zoltán Szigeti,