Biblioteca Digital do Instituto Politécnico de Bragança   Instituto Politécnico de Bragança

Biblioteca Digital do IPB >
Escola Superior de Tecnologia e Gestão >
Matemática >
DEMAT - Publicações em Proceedings Indexadas ao ISI/Scopus >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10198/1271

Título: Recognition of graphs with convex quadratic stability number
Autor: Pacheco, Maria F.
Cardoso, Domingos M.
Palavras-chave: Graph theory
Convex optimization
Issue Date: 2009
Editora: American Institute of Physics
Citação: Pacheco, 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.
Resumo: A 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.
URI: http://hdl.handle.net/10198/1271
ISBN: 978-0-7354-0709
Versão do Editor: http://scitation.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=APCPCS001168000001001366000001&idtype=cvips
Appears in Collections:DEMAT - Publicações em Proceedings Indexadas ao ISI/Scopus

Files in This Item:

File Description SizeFormat
Recognition of Graphs with Convex Quadratic Stability number.pdf289,12 kBAdobe PDFView/Open

Please give feedback about this item
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

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

 


© Instituto Politécnico de Bragança - Biblioteca Digital - Feedback - Statistics
Promotores do RCAAP   Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência PO Sociedade do Conhecimento (POSC) Portal oficial da União Europeia