New results for recognizing convex-QP adverse graphs. (2nd January 2020)

• Record Type: Journal Article
• Authors: Luz, Carlos J.
• Is Part Of: Optimization. Volume 69:Number 1(2020)
• Page Start: 131
• Page End: 144
• Publication Date: 2020-01-02
• Subjects: Convex quadratic programming in graphs -- maximum stable set -- combinatorial optimization -- graph theory; 90C35 -- 90C20 -- 05C69 -- 90C27 -- 68R10; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2018.1556664
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: A graph G with convex- QP stability number (or simply a convex- QP graph) is a graph for which the stability number is equal to the optimal value of a convex quadratic programme, say P ( G ) . The problem of recognizing in polynomial time whether or not a given graph is a convex- QP graph has resisted to be completely solved. In this paper, some progress recently made for trying to settle this open question is reported. Namely, if G is a graph such that the optimal solutions of P ( G ) are critical points of the objective function, some new necessary and sufficient conditions for G to be a convex- QP graph are proved. The practical value of two of these results is also exemplified.