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

共 50 条

[41] Practical Access to Dynamic Programming on Tree Decompositions
Bannach, Max
Berndt, Sebastian
ALGORITHMS, 2019, 12 (08)
[42] GRAPH DECOMPOSITIONS AND TREE AUTOMATA IN REASONING WITH UNCERTAINTY
ARNBORG, S
JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 1993, 5 (04) : 335 - 357
[43] Decompositions of minimum rank matrices
Barrett, Wayne
Kempton, Mark
Malloy, Nicole
Nelson, Curtis
Sexton, William
Sinkovic, John
LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 438 (10) : 3913 - 3948
[44] Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata
Blume, Christoph
Bruggink, H. J. Sander
Friedrich, Martin
Koenig, Barbara
JOURNAL OF VISUAL LANGUAGES AND COMPUTING, 2013, 24 (03) : 192 - 206
[45] A note on the tree decompositions of graphs
SHI MinyongInstitute of Software
Chinese Science Bulletin, 1997, (23) : 1948 - 1952
[46] A note on the tree decompositions of graphs
Shi, MY
CHINESE SCIENCE BULLETIN, 1997, 42 (23): : 1948 - 1952
[47] Induced subgraphs and tree decompositions VII Basic obstructions in H-free graphs .
Abrishami, Tara
Alecu, Bogdan
Chudnovsky, Maria
Hajebi, Sepehr
Spirkl, Sophie
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 164 : 443 - 472
[48] Expansion-based QBF Solving on Tree Decompositions
Charwat, Guenther
Woltran, Stefan
FUNDAMENTA INFORMATICAE, 2019, 167 (1-2) : 59 - 92
[49] Tree decompositions for a class of graphs
Shi, MY
Li, YJ
Tian, F
DISCRETE MATHEMATICS, 1998, 189 (1-3) : 221 - 232
[50] Reachability Analysis Using Message Passing over Tree Decompositions
Sankaranarayanan, Sriram
COMPUTER AIDED VERIFICATION (CAV 2020), PT I, 2020, 12224 : 604 - 628

← 1 2 3 4 5 →