Show simple item record

An FPT 2-Approximation for Tree-cut Decomposition

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
hal.structure.identifier
dc.contributor.authorOum, Sang-Il
hal.structure.identifier
dc.contributor.authorPaul, Christophe
HAL ID: 4726
hal.structure.identifier
dc.contributor.authorSau Valls, Ignasi
HAL ID: 7331
ORCID: 0000-0002-8981-9287
hal.structure.identifier
dc.contributor.authorThilikos, Dimitrios M.
HAL ID: 178742
ORCID: 0000-0003-0470-1800
dc.date.accessioned2020-09-29T15:53:28Z
dc.date.available2020-09-29T15:53:28Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21013
dc.descriptionLecture Notes in Computer Science 9499en
dc.language.isoenen
dc.subjectFixed-parameter tractable algorithmen
dc.subjectTree-cut widthen
dc.subjectApproximation algorithmen
dc.subject.ddc005en
dc.titleAn FPT 2-Approximation for Tree-cut Decompositionen
dc.typeCommunication / Conférence
dc.description.abstractenThe tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47–66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2w, in time 2O(w2logw)⋅n2 . Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known.en
dc.identifier.citationpages35-46en
dc.relation.ispartoftitleApproximation and Online Algorithmsen
dc.relation.ispartofeditorSanità, Laura
dc.relation.ispartofeditorSkutella, Martin
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofurl10.1007/978-3-319-28684-6en
dc.identifier.urlsitehttps://hal-lirmm.ccsd.cnrs.fr/lirmm-01264015en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-319-28683-9en
dc.relation.conftitleApproximation and Online Algorithms 13th International Workshop, WAOA 2015en
dc.relation.confdate2015-09
dc.relation.confcityPatrasen
dc.relation.confcountryGreeceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-28684-6_4en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-09-25T13:38:13Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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