A simplex like approach based on star sets for recognizing convex- $$QP$$ Q P adverse graphs

Domingos M. Cardoso () and Carlos J. Luz ()
Additional contact information
Domingos M. Cardoso: University of Aveiro
Carlos J. Luz: University of Aveiro

Journal of Combinatorial Optimization, 2016, vol. 31, issue 1, No 20, 326 pages

Abstract: Abstract A graph $$G$$ G with convex- $$QP$$ Q P stability number (or simply a convex- $$QP$$ Q P graph) is a graph for which the stability number is equal to the optimal value of a convex quadratic program, say $$P(G)$$ P ( G ) . There are polynomial-time procedures to recognize convex- $$QP$$ Q P graphs, except when the graph $$G$$ 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)$$ P ( G ) are both integer and none of them changes when the neighborhood of any vertex of $$G$$ G is deleted). In this paper, from a characterization of convex- $$QP$$ Q P graphs based on star sets associated to the least eigenvalue of its adjacency matrix, a simplex-like algorithm for the recognition of convex- $$QP$$ Q P adverse graphs is introduced.

Keywords: Convex quadratic programming in graphs; Star sets; Graphs with convex- $$QP$$ Q P stability number; Simplex-like approach (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9745-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:1:d:10.1007_s10878-014-9745-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9745-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().