On the commutativity of antiblocker diagrams under lift-and-project operators (Q2500533): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2006.03.026 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2015198705 / rank | |||
Normal rank |
Revision as of 22:56, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the commutativity of antiblocker diagrams under lift-and-project operators |
scientific article |
Statements
On the commutativity of antiblocker diagrams under lift-and-project operators (English)
0 references
17 August 2006
0 references
The behaviour of the disjunctive operator in the context of the ``antiblocker duality diagram'' associated with the stable set polytope, \(\text{QSTAB}(G)\), of a graph and its complement has been studied by \textit{N. Aguilera, M. Escalante} and \textit{G. Nasini} [Math. Oper. Res. 27, 460--469 (2002; Zbl 1083.05505)]. The main consequence of this work is a generalization of the perfect graph theorem under disjunctive rank. The behaviour of the lift-and-project operators \(N_0, N\) and \(N_{+}\) has been studied by Lipták and Tunçel. They found an example of graph for which the diagram does not commute in one iteration of the \(N_0, N\) and \(N_{+}\) operator. In the present paper the authors give, for any number of iterations, explicit proofs of noncommutativity of the \(N_0, N\) and \(N_{+}\) diagram. In the particular case of the \(N_0\) and \(N\) operator, they found exact bounds for the ranks of the complements of line graphs (of complete graphs).
0 references
stable set problem
0 references
antiblocker duality
0 references
disjunctive rank
0 references