Skip to Main content Skip to Navigation
New interface
Journal articles

Minimum Size Tree-Decompositions

Bi Li 1 Fatima Zahra Moataz 2 Nicolas Nisse 2 Karol Suchan 3, 4 
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed $k ≥ 1$, what is the complexity of computing a tree-decomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed $k ≥ $4 and polynomial for $k ≤ 2$; for $k = 3$, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Thursday, November 23, 2017 - 3:26:18 PM
Last modification on : Thursday, August 4, 2022 - 4:58:25 PM


Files produced by the author(s)



Bi Li, Fatima Zahra Moataz, Nicolas Nisse, Karol Suchan. Minimum Size Tree-Decompositions. Discrete Applied Mathematics, 2017, ⟨10.1016/j.dam.2017.01.030⟩. ⟨hal-01620389⟩



Record views


Files downloads