Minimum size tree-decompositions

被引：2

作者：

Li, Bi ^{[3
]}

Moataz, Fatima Zahra ^{[1
,2
]}

Nisse, Nicolas ^{[1
,2
]}

Suchan, Karol ^{[4
,5
]}

机构：

[1] INRIA, Rennes, France

[2] Univ Nice Sophia Antipolis, CNRS, UMR 7271, I3S, Sophia Antipolis, France

[3] Xidian Univ, Sch Math & Stat, Xian, Shaanxi, Peoples R China

[4] Univ Adolfo Ibanez, Santiago, Chile

[5] AGH Univ Sci & Technol, Krakow, Poland

来源：

DISCRETE APPLIED MATHEMATICS | 2018年 / 245卷

关键词：

Tree-decomposition; Treewidth; NP-hard; PARTIAL; 3-TREES; RECOGNITION; COMPLEXITY; TREEWIDTH; GRAPHS; WIDTH;

D O I：

10.1016/j.dam.2017.01.030

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：109 / 127

页数：19

共 18 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES [J].