W-Hardness Under Linear FPT-Reductions: Structural Properties and Further Applications

摘要：

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 Wt-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.

作者: Jianer Chen Xiuzhen Huang Iyad A. Kanj Ge Xia

作者单位: Dept. of Computer Science, Texas A&M University, College Station, TX 77843 College of Information Sc Computer Science Department, Arkansas State University, State University, Arkansas 72467, USA School of Computer Science, Telecommunications and Information Systems DePaul University, 243 S. Wab Department of Computer Science, Lafayette College, Easton, PA 18042, USA

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 975-984

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）