W-hardness under linear FPT-reductions: Structural properties and further applications Conference Paper

abstract

• The notion of linear fpt-reductions has been recently used to derive strong computational lower bounds for well-known NP-hard problems. In this paper, we formally investigate the notions of W[t]-hardness and W[t]-completeness under the linear fpt-reduction, and study structural properties of the corresponding complexity classes. Additional complexity lower bounds on important computational problems are also established. Springer-Verlag Berlin Heidelberg 2005.

authors

• Chen, Jianer

published proceedings

• COMPUTING AND COMBINATORICS, PROCEEDINGS

author list (cited authors)

• Chen, J., Huang, X. Z., Kanj, I. A., & Xia, G.

complete list of authors

• Chen, J||Huang, XZ||Kanj, IA||Xia, G

publication date

• October 2005

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 10

• 3-540-28061-8

start page

• 975

end page

• 984

volume

• 3595