• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

An FPT 2-Approximation for Tree-Cut Decomposition

Thumbnail
Date
2018
Link to item file
https://arxiv.org/abs/1509.04880v1
Dewey
Modèles mathématiques. Algorithmes
Sujet
Fixed-parameter tractable algorithm; Tree-cut width; Approximation algorithm
Journal issue
Algorithmica
Volume
80
Number
1
Publication date
01-2018
Article pages
116-135
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00453-016-0245-5
URI
https://basepub.dauphine.fr/handle/123456789/19025
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Oum, Sang-il
107170 Department of Mathematical Sciences, KAIST
Paul, Christophe
181 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Sau Valls, Ignasi
181 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Thilikos, Dimitrios M.
233371 Computer Technology Institute and Press "Diophantus"
Type
Article accepté pour publication ou publié
Abstract (EN)
The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.