Ubiquitous parameterization - Invitation to fixed-parameter algorithms

被引：0
作者：
Niedermeier, R [1 ]
机构：
[1] Univ Tubingen, Wilhelm Schickard Inst Informat, D-72076 Tubingen, Germany
来源：
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS | 2004年 / 3153卷
关键词：
NP-hardness; parameterized complexity; fixed-parameter algorithms; parameterization;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Problem parameters are ubiquitous. In every area of computer science, we find all kinds of "special aspects" to the problems encountered. Hence, the study of parameterized complexity for computationally hard problems is proving highly fruitful. The purpose of this article is to stir the reader's interest in this field by providing a gentle introduction to the rewarding field of fixed-paxameter algorithms.
引用
收藏
页码：84 / 103
页数：20
相关论文
共 86 条
[1]  
ABUKHZAM FN, 2004, P ALENEX04 ACM SIAM
[2]   Graph separators: a parameterized view [J].
Alber, J ;
Fernau, H ;
Niedermeier, R .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) :808-832
[3]  
Alber J, 2001, LECT NOTES COMPUT SC, V2136, P111
[4]  
Alber J, 2002, LECT NOTES COMPUT SC, V2368, P150
[5]   Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs [J].
Alber, J ;
Bodlaender, HL ;
Fernau, H ;
Kloks, T ;
Niedermeier, R .
ALGORITHMICA, 2002, 33 (04) :461-493
[6]   Faster exact algorithms for hard problems: A parameterized point of view [J].
Alber, J ;
Gramm, J ;
Niedermeier, R .
DISCRETE MATHEMATICS, 2001, 229 (1-3) :3-27
[7]  
Alber J, 2001, LECT NOTES COMPUT SC, V2076, P261
[8]  
ALBER J, 2004, IN PRESS DISCRETE AP
[9]  
ALBER J, 2003, P INT NETW OPT C INO, P1
[10]  
ALBER J, 2003, THESIS U TUBINGEN GE
123456789