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