Minimum size tree-decompositions
Li
B
author
Moataz
F
Z
author
Nisse
N
author
Suchan
K
author
2018
English
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. (C) 2017 Elsevier B.V. All rights reserved.
Tree-decomposition
Treewidth
NP-hard
WOS:000435046700011
exported from refbase (show.php?record=874), last updated on Tue, 24 Jul 2018 16:04:05 -0400
text
files/864_Li_etal2018.pdf
10.1016/j.endm.2015.07.005
Li_etal2018
Discrete Applied Mathematics
Discret Appl. Math.
2018
Elsevier Science Bv
continuing
periodical
academic journal
245
109
127
0166-218x