| dc.contributor.author | Bazgan, Cristina | |
| dc.contributor.author | Tuza, Zsolt | |
| dc.contributor.author | Vanderpooten, Daniel | |
| dc.date.accessioned | 2009-09-08T09:11:41Z | |
| dc.date.available | 2009-09-08T09:11:41Z | |
| dc.date.issued | 2007 | |
| dc.identifier.issn | 0166-218X | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/1509 | |
| dc.language.iso | en | en |
| dc.subject | Polynomial algorithm | |
| dc.subject | Graph decomposition | |
| dc.subject | Vertex partition | |
| dc.subject | Vertex degree | |
| dc.subject.ddc | 005 | en |
| dc.title | Efficient algorithms for decomposing graphs under degree constraints | |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321–324] proved that if every vertex v in a graph G has degree d(v)greater-or-equal, slanteda(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that dA(v)greater-or-equal, slanteda(v) for every vset membership, variantA and dB(v)greater-or-equal, slantedb(v) for every vset membership, variantB. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7–9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237–239] strengthened this result, proving that it suffices to assume d(v)greater-or-equal, slanteda+b (a,bgreater-or-equal, slanted1) or just d(v)greater-or-equal, slanteda+b-1 (a,bgreater-or-equal, slanted2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented. | |
| dc.relation.isversionofjnlname | Discrete Applied Mathematics | |
| dc.relation.isversionofjnlvol | 155 | |
| dc.relation.isversionofjnlissue | 8 | |
| dc.relation.isversionofjnldate | 2007 | |
| dc.relation.isversionofjnlpages | 979-988 | |
| dc.relation.isversionofdoi | http://dx.doi.org/10.1016/j.dam.2006.10.005 | |
| dc.description.sponsorshipprivate | oui | en |
| dc.relation.isversionofjnlpublisher | Elsevier | |
| dc.subject.ddclabel | Programmation, logiciels, organisation des données | en |
| dc.description.ssrncandidate | non | |
| dc.description.halcandidate | oui | |
| dc.description.readership | recherche | |
| dc.description.audience | International | |
| dc.relation.Isversionofjnlpeerreviewed | oui | |
| dc.date.updated | 2016-10-06T09:49:01Z | |
