|   | 
Author Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K.
Title Minimum size tree-decompositions Type
Year 2018 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 245 Issue Pages 109-127
Keywords Tree-decomposition; Treewidth; NP-hard
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. (C) 2017 Elsevier B.V. All rights reserved.
Address [Moataz, Fatima Zahra; Nisse, Nicolas] INRIA, Rennes, France, Email: nicolas.nisse@inria.fr
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000435046700011 Approved
Call Number UAI @ eduardo.moreno @ Serial 874
Permanent link to this record