Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorTuza, Zsolt
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-04-13T10:15:15Z
dc.date.available2010-04-13T10:15:15Z
dc.date.issued2006
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3957
dc.language.isoenen
dc.subjectPolynomial Algorithm
dc.subjectTreewidth
dc.subjectGraph decomposition
dc.subjectPlanar graphs
dc.subjectPTAS
dc.subject.ddc003en
dc.titleDegree-constrained decompositions of graphs: bounded treewidth and planarity
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study the problem of decomposing the vertex set V of a graph into two nonempty parts V1,V2 which induce subgraphs where each vertex vset membership, variantV1 has degree at least a(v) inside V1 and each vset membership, variantV2 has degree at least b(v) inside V2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol355
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2006
dc.relation.isversionofjnlpages389-395
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2006.01.024
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:58:18Z


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