Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness  

作　　者：Jian-ErChen 

机构地区：[1]CollegeofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,P.R.China

出　　处：《Journal of Computer Science & Technology》2005年第1期18-37,共20页计算机科学技术学报（英文版）

基　　金：国家自然科学基金，教育部长江学者奖励计划

摘　　要：The theory of parameterized computation and complexity is a recentlydeveloped subarea in theoretical computer science. The theory is aimed at practically solving alarge number of computational problems that are theoretically intractable. The theory is based onthe observation that many intractable computational problems in practice are associated with aparameter that varies within a small or moderate range. Therefore, by taking the advantages of thesmall parameters, many theoretically intractable problems can be solved effectively and practically.On the other hand, the theory of parameterized computation and complexity has also offered powerfultechniques that enable us to derive strong computational lower bounds for many computationalproblems, thus explaining why certain theoretically tractable problems cannot be solved effectivelyand practically. The theory of parameterized computation and complexity has found wide applicationsin areas such as database systems, programming languages, networks, VLSI design, parallel anddistributed computing, computational biology, and robotics. This survey gives an overview on thefundamentals, algorithms, techniques, and applications developed in the research of parameterizedcomputation and complexity. We will also report the most recent advances and excitements, anddiscuss further research directions in the area.The theory of parameterized computation and complexity is a recentlydeveloped subarea in theoretical computer science. The theory is aimed at practically solving alarge number of computational problems that are theoretically intractable. The theory is based onthe observation that many intractable computational problems in practice are associated with aparameter that varies within a small or moderate range. Therefore, by taking the advantages of thesmall parameters, many theoretically intractable problems can be solved effectively and practically.On the other hand, the theory of parameterized computation and complexity has also offered powerfultechniques that enable us to derive strong computational lower bounds for many computationalproblems, thus explaining why certain theoretically tractable problems cannot be solved effectivelyand practically. The theory of parameterized computation and complexity has found wide applicationsin areas such as database systems, programming languages, networks, VLSI design, parallel anddistributed computing, computational biology, and robotics. This survey gives an overview on thefundamentals, algorithms, techniques, and applications developed in the research of parameterizedcomputation and complexity. We will also report the most recent advances and excitements, anddiscuss further research directions in the area.

关 键 词：ALGORITHM computational complexity NP-COMPLETENESS parameterizedcomputation approximation algorithm 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]