A simplex like approach based on star sets for recognizing convex-QP adverse graphs |
| |
Authors: | Domingos M Cardoso Carlos J Luz |
| |
Institution: | 1. Center for Research and Development in Mathematics and Applications, Department of Mathematics, University of Aveiro, Aveiro, Portugal 2. Center for Research and Development in Mathematics and Applications, University of Aveiro, Aveiro, Portugal
|
| |
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 program, say \(P(G)\). There are polynomial-time procedures to recognize convex-\(QP\) graphs, except when the graph \(G\) is adverse or contains an adverse subgraph (that is, a non complete graph, without isolated vertices, such that the least eigenvalue of its adjacency matrix and the optimal value of \(P(G)\) are both integer and none of them changes when the neighborhood of any vertex of \(G\) is deleted). In this paper, from a characterization of convex-\(QP\) graphs based on star sets associated to the least eigenvalue of its adjacency matrix, a simplex-like algorithm for the recognition of convex-\(QP\) adverse graphs is introduced. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|