Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/27479
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cardoso, Domingos M. | pt_PT |
dc.date.accessioned | 2020-02-04T17:54:23Z | - |
dc.date.available | 2020-02-04T17:54:23Z | - |
dc.date.issued | 2020-01 | - |
dc.identifier.issn | 0233-1934 | pt_PT |
dc.identifier.uri | http://hdl.handle.net/10773/27479 | - |
dc.description.abstract | A graph with convex quadratic stability number is a graph for which the stability number is determined by solving a convex quadratic program. Since the very beginning, where a convex quadratic programming upper bound on the stability number was introduced, a necessary and sufficient condition for this upper bound be attained was deduced. The recognition of graphs with convex quadratic stability number has been deeply studied with several consequences from continuous and combinatorial point of view. This survey starts with an exposition of some extensions of the classical Motzkin-Straus approach to the determination of the stability number of a graph and its relations with the convex quadratic programming upper bound. The main advances, including several properties and alternative characterizations of graphs with convex quadratic stability number are described as well as the algorithmic strategies developed for their recognition. Open problems and a conjecture for a particular class of graphs, herein called adverse graphs, are presented, pointing out a research line which is a challenge between continuous and discrete problems. | pt_PT |
dc.language.iso | eng | pt_PT |
dc.publisher | Taylors & Fancis | pt_PT |
dc.relation | info:eu-repo/grantAgreement/FCT/5876/147206/PT | pt_PT |
dc.rights | restrictedAccess | pt_PT |
dc.subject | Convex quadratic programming in graphs | pt_PT |
dc.subject | Stability number of graphs | pt_PT |
dc.subject | Relations between continuous and discrete optimization | pt_PT |
dc.title | A survey on graphs with convex quadratic stability number | pt_PT |
dc.type | article | pt_PT |
dc.description.version | published | pt_PT |
dc.peerreviewed | yes | pt_PT |
degois.publication.firstPage | 5 | pt_PT |
degois.publication.issue | 1 | pt_PT |
degois.publication.lastPage | 20 | pt_PT |
degois.publication.title | Optimization | pt_PT |
degois.publication.volume | 69 | pt_PT |
dc.relation.publisherversion | https://www.tandfonline.com/doi/full/10.1080/02331934.2018.1526282 | pt_PT |
dc.identifier.doi | 10.1080/02331934.2018.1526282 | pt_PT |
dc.identifier.essn | 1029-4945 | pt_PT |
Appears in Collections: | CIDMA - Artigos DMat - Artigos OGTCG - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
A survey on graphs with convex quadratic stability number.pdf | 1.62 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.