Repository logo
 
Publication

Recognition of graphs with convex quadratic stability number

2009Conference object Open access
Simple item page
dc.contributor.authorPacheco, Maria F.
dc.contributor.authorCardoso, Domingos M.
dc.date.accessioned2010-01-12T16:59:01Z
dc.date.available2010-01-12T16:59:01Z
dc.date.issued2009
dc.description.abstractA stable set of a graph is a set of mutually non-adjacent vertices. The determination of a maximum size stable set, which is called maximum stable set, and the determination of its size, which is called stability number, are central combinatorial optimization problems. However, given a nonnegative integer k, to determine if a graph G has a stable set of size k is NP-complete. In this paper we deal with graphs for which the stability number can be determined by solving a convex quadratic programming problem. Such graphs were introduced in [13] and are called graphs with convex-QP stability number. A few algorithmic techniques for the recognition of this type of graphs in particular families are presented.pt
dc.identifier.citationPacheco, Maria F.; Cardoso, Domingos M. (2009). Recognition of graphs with convex quadratic stability number. In AIP Conference Proceedings - International Conference on Numerical Analysis and Applied Mathematics. p.1366-1369. ISBN 978-0-7354-0709.pt
dc.identifier.isbn978-0-7354-0709
dc.identifier.urihttp://hdl.handle.net/10198/1271
dc.language.isoengpt
dc.publisherAmerican Institute of Physicspt
dc.relation.publisherversionhttp://scitation.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=APCPCS001168000001001366000001&idtype=cvipspt
dc.subjectGraph theorypt
dc.subjectConvex optimizationpt
dc.titleRecognition of graphs with convex quadratic stability numberpt
dc.typeconference object
dspace.entity.typePublication
oaire.citation.conferencePlaceInternational Conference on Numerical Analysis and Applied Mathematics 2009pt
oaire.citation.endPage1369pt
oaire.citation.startPage1366pt
oaire.citation.titleAIP Conference Proceedingspt
person.familyNamePacheco
person.givenNameMaria F.
person.identifier.ciencia-idF319-DAC3-8F15
person.identifier.orcid0000-0001-7915-0391
person.identifier.scopus-author-id36802474600
rcaap.rightsopenAccesspt
rcaap.typeconferenceObjectpt
relation.isAuthorOfPublicatione56596ca-3238-4fde-ace1-abb363a222e8
relation.isAuthorOfPublication.latestForDiscoverye56596ca-3238-4fde-ace1-abb363a222e8

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Recognition of Graphs with Convex Quadratic Stability number.pdf
Size:
289.12 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.83 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

ESTiG - Publicações em Proceedings Indexadas à WoS/Scopus