Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/4439
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cardoso, Domingos M. | pt |
dc.contributor.author | Kaminski, Marcin | pt |
dc.contributor.author | Lozin, Vadim | pt |
dc.date.accessioned | 2011-11-28T16:57:19Z | - |
dc.date.issued | 2007 | - |
dc.identifier.issn | 1382-6905 | pt |
dc.identifier.uri | http://hdl.handle.net/10773/4439 | - |
dc.description.abstract | Independent sets, induced matchings and cliques are examples of regular induced subgraphs in a graph. In this paper, we prove that finding a maximum cardinality k-regular induced subgraph is an NP-hard problem for any fixed value of k. We propose a convex quadratic upper bound on the size of a k-regular induced subgraph and characterize those graphs for which this bound is attained. Finally, we extend the Hoffman bound on the size of a maximum 0-regular subgraph (the independence number) from k = 0 to larger values of k. | pt |
dc.description.sponsorship | CEOC | pt |
dc.description.sponsorship | FCT | pt |
dc.description.sponsorship | FEDER/POCI 2010 | pt |
dc.language.iso | eng | pt |
dc.publisher | Springer Verlag | pt |
dc.rights | restrictedAccess | por |
dc.subject | Graphs | pt |
dc.subject | Independent sets | pt |
dc.subject | Induced matchings | pt |
dc.subject | Hamiltonian cycles | pt |
dc.title | Maximum k-regular induced subgraphs | pt |
dc.type | article | pt |
dc.peerreviewed | yes | pt |
ua.distribution | international | pt |
degois.publication.firstPage | 455 | pt |
degois.publication.issue | 4 | pt |
degois.publication.lastPage | 463 | pt |
degois.publication.title | Journal of Combinatorial Optimization | pt |
degois.publication.volume | 14 | pt |
dc.date.embargo | 10000-01-01 | - |
dc.relation.publisherversion | http://www.springerlink.com/content/q510000166707781/ | * |
Appears in Collections: | DMat - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CardosoLozin2007.pdf | Electronic Version | 291.01 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.