Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/17120
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCardoso, Domingos Moreirapt
dc.contributor.authorPinheiro, Sofia J.pt
dc.date.accessioned2017-04-03T13:25:25Z-
dc.date.issued2017-03-
dc.identifier.isbn978-3-319-49982-6pt
dc.identifier.urihttp://hdl.handle.net/10773/17120-
dc.description.abstractMany optimization problems on graphs are reduced to the determination of a subset of vertices of maximum cardinality which induces a $k$-regular subgraph. For example, a maximum independent set, a maximum induced matching and a maximum clique is a maximum cardinality $0$-regular, $1$-regular and $(\omega(G)-1)$-regular induced subgraph, respectively, were $\omega(G)$ denotes the clique number of the graph $G$. The determination of the order of a $k$-regular induced subgraph of highest order is in general an NP-hard problem. This paper is devoted to the study of spectral upper bounds on the order of these subgraphs which are determined in polynomial time and in many cases are good approximations of the respective optimal solutions. The introduced upper bounds are deduced based on adjacency, Laplacian and signless Laplacian spectra. Some analytical comparisons between them are presented. Finally, all of the studied upper bounds are tested and compared through several computational experiments.pt
dc.language.isoengpt
dc.publisherSpringerpt
dc.relationFCT - UID/MAT/04106/2013pt
dc.rightsopenAccesspor
dc.subjectSpectral graph theorypt
dc.subjectMaximum k-regular induced subgraphspt
dc.subjectCombinatorial optimizationpt
dc.titleSpectral bounds for the k-regular induced subgraph problempt
dc.typebookPartpt
degois.publication.firstPage105pt
degois.publication.issue7pt
degois.publication.lastPage116pt
degois.publication.locationCham, Switzerlandpt
degois.publication.titleApplied and Computational Matrix Analysispt
dc.date.embargo2019-02-23T14:00:00Z-
dc.identifier.doi10.1007/978-3-319-49984-0_7pt
Appears in Collections:CIDMA - Capítulo de livro
OGTCG - Capítulo de livro

Files in This Item:
File Description SizeFormat 
CardosoPinheiro_MatTriad_2015_R.pdfpre-print: approved version82.19 kBAdobe PDFView/Open


FacebookTwitterLinkedIn
Formato BibTex MendeleyEndnote Degois 

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