On Parameterized Exponential Time Complexity Conference Paper

abstract

• In this paper, we show that special instances of parameterized NP-hard problems are as difficult as the general instances in terms of their subexponential time computability. For example, we show that the Planar Dominating Set problem on degree-3 graphs can be solved in 2(k)p(n) parameterized time if and only if the general Planar Dominating Set problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well. Springer-Verlag Berlin Heidelberg 2009.

name of conference

• Theory and Applications of Models of Computation, 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings

authors

• Chen, Jianer

published proceedings

• THEORY AND APPLICATIONS OF MODELS OF COMPUTATION

author list (cited authors)

• Chen, J., Kanj, I. A., & Ge, X.

citation count

• 0

complete list of authors

• Chen, Jianer||Kanj, Iyad A||Ge, Xia

publication date

• July 2009

publisher

• Springer Nature  Publisher

published in

• Lecture Notes in Artificial Intelligence  Journal

keywords

• 46 Information And Computing Sciences

Digital Object Identifier (DOI)

• 10.1007/978-3-642-02017-9_20

International Standard Book Number (ISBN) 13

• 978-3-642-02016-2

start page

• 168

end page

• +

volume

• 5532

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-3-642-02017-9_20