Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/15192
Title: A simplex like approach based on star sets for recognizing convex-QP adverse graphs
Author: Cardoso, Domingos M.
Luz, Carlos J.
Keywords: Convex quadratic programming in graphs
Star sets
Graphs with convex-QP stability number
Simplex-like approach
Issue Date: Jan-2016
Publisher: Springer
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.
Peer review: yes
URI: http://hdl.handle.net/10773/15192
DOI: 10.1007/s10878-014-9745-x
ISSN: 1382-6905
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
art_10.1007_s10878-014-9745-x.pdfPrinted version - full text404.58 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.