| |
Record |
Links |
|
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 |
