• Title of article

    Covering symmetric semi-monotone functions

  • Author/Authors

    Roland Grappe، نويسنده , , Zolt?n Szigeti، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2008
  • Pages
    7
  • From page
    138
  • To page
    144
  • 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 image 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
    Edge-connectivity augmentation , Skew-supermodular functions
  • Journal title
    Discrete Applied Mathematics
  • Serial Year
    2008
  • Journal title
    Discrete Applied Mathematics
  • Record number

    886642