• 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
2015
Notes
Lecture Notes in Computer Science 9499
Link to item file
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264015
Dewey
Programmation, logiciels, organisation des données
Sujet
Fixed-parameter tractable algorithm; Tree-cut width; Approximation algorithm
DOI
http://dx.doi.org/10.1007/978-3-319-28684-6_4
Conference name
Approximation and Online Algorithms 13th International Workshop, WAOA 2015
Conference date
09-2015
Conference city
Patras
Conference country
Greece
Book title
Approximation and Online Algorithms
Author
Sanità, Laura; Skutella, Martin
Publisher
Springer
Publisher city
Berlin Heidelberg
ISBN
978-3-319-28683-9
Book URL
10.1007/978-3-319-28684-6
URI
https://basepub.dauphine.fr/handle/123456789/21013
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
Paul, Christophe
Sau Valls, Ignasi
Thilikos, Dimitrios M.
Type
Communication / Conférence
Item number of pages
35-46
Abstract (EN)
The 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.

  • 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.