@inproceedings{92f925c0ae774f7faaafc881e093b6ca,

title = "Subexponential time algorithms for finding small tree and path decompositions",

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/ logn) time and show that they cannot be solved in 2^o(n / logn) time, assuming the Exponential Time Hypothesis.",

author = "H.L. Bodlaender and J. Nederlof",

year = "2015",

doi = "10.1007/978-3-662-48350-3_16",

language = "English",

isbn = "978-3-662-48349-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "179--190",

editor = "N. Bansal and I. Finocchi",

booktitle = "Algorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015)",

address = "Germany",

}