Akademska digitalna zbirka SLovenije - logo
E-resources
Peer reviewed Open access
  • On exact blockers and anti-...
    Gurvich, Vladimir

    Discrete Applied Mathematics, 03/2011, Volume: 159, Issue: 5
    Journal Article

    Let us consider two binary systems of inequalities (i) C x ≥ e and (ii) C x ≤ e , where C ∈ { 0 , 1 } m × n is an m × n ( 0 , 1 ) -matrix, x ∈ { 0 , 1 } n , and e is the vector of m ones. The set of all support-minimal (respectively, support-maximal) solutions x to (i) (respectively, to (ii)) is called the blocker (respectively, anti-blocker). A blocker B (respectively, anti-blocker A ) is called exact if C x = e for every x ∈ B (respectively, x ∈ A ). Exact blockers can be completely characterized. There is a one-to-one correspondence between them and P 4 -free graphs (along with a well-known one-to-one correspondence between the latter and the so-called read-once Boolean functions). However, the class of exact anti-blockers is wider and more sophisticated. We demonstrate that it is closely related to the so-called CIS graphs, more general ℓ -CIS d -graphs, and Δ -conjecture.