Name
Abstract | ||
|---|---|---|
The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k >= 4. In this paper we present algorithms that solve both problems for fixed k in 2(O(n/) (log n)) time and show that they cannot be solved in 2(o(n/) (log n)) time, assuming the Exponential Time Hypothesis. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-662-48350-3_16 | ALGORITHMS - ESA 2015 |
Field | DocType | Volume |
Integer,Graph,Discrete mathematics,Combinatorics,Ask price,Graph isomorphism,Tree decomposition,Algorithm,Isomorphism class,Mathematics,Exponential time hypothesis | Journal | 9294 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.41 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans L. Bodlaender | 1 | 5699 | 375.15 |
| Jesper Nederlof | 2 | 294 | 24.22 |