Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorTuza, Zsolt
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2009-09-08T09:11:41Z
dc.date.available2009-09-08T09:11:41Z
dc.date.issued2007
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/1509
dc.language.isoenen
dc.subjectPolynomial algorithm
dc.subjectGraph decomposition
dc.subjectVertex partition
dc.subjectVertex degree
dc.subject.ddc005en
dc.titleEfficient algorithms for decomposing graphs under degree constraints
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenStiebitz [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.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol155
dc.relation.isversionofjnlissue8
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages979-988
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2006.10.005
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:49:01Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record