参数计算中使用的若干技术

摘要/Abstract

摘要： 参数计算和复杂性是上世纪末本世纪初兴起的一门技术。该技术因具有坚实的理论基础和良好的运行效果,故仅经过短短十几年的发展,已经取得了大量的成就。从趋势上看来,参数计算已经成为理论计算机科学中越来越热门的一个分支。先简要介绍参数计算和复杂性的重要理论基础和主要思想；之后重点介绍参数计算中使用的主要技术, 分析每一种技术的功能作用、基本设计原则和优缺点,并结合简单案例加以说明。

关键词: 参数计算,复杂性,NP完全,核心化,分支搜索中图法分类号TP301．6文献标识码A

Abstract: Parameterized computation and complexity are one of the techniques arised in the end of last century and the beginning of the current one．Because of its solid theoretical foundation and excellent running performance,it has achieved much success despite of its short-time development．In a trend,parameterized computation is becoming a hotter and hotter branch of computer science．This paper first introducesd the important theoretical base and key idea of parameterized computation,then mainly introduced the key techniques used in it,introduced its function,basic design principles and advantages/disadvantages for every technique,and used simple examples to explain it.

Key words: Parameterized computation,Complexity,NP-complete,Kernelization,Branch and search

周星,彭伟. 参数计算中使用的若干技术[J]. 计算机科学, 2014, 41(Z6): 18-23. https://doi.org/

ZHOU Xing and PENG Wei. Several Techniques Used in Parameterized Computation[J]. Computer Science, 2014, 41(Z6): 18-23. https://doi.org/

参考文献

[1] Graey M R,Jonhnson D S．Computers and Intractability:AGuide to the Theory of NP-Completeness[M]．New York:W．H．Freeman and Company,1979
[2] Chen Jia-ner．Parameterized computation and complexity:a new approach dealing with NP-hardness[J]．Journal of Computer Science and Technology,2005,0:18-37
[3] Ausiello G,Cresenzi P,Gambosi G,et al．Complexity and Ap-proximation[M]．Springer-Verlag,1999
[4] Hochbaum D S．Approximation algorithms for NP-hard pro-blems[M]．Boston,MA:PWS Publishing Company,1997
[5] Pearl J.Heuristics[M]．Addison-Wesley Pub,1984
[6] Michalewicz Z,Fogel D B．How to Solve It:Modem Heuristics[M]．Springer-Verlag,2000
[7] Motwani R,Raghavan P．Randomized Algorithms[M]．Cam-bridge University Press,1995
[8] Mitzenmacher M,Upfal E．Probability and Computing:Randomized Algorithms and probabilistic Analysis[M]． New York(NY):Cambridge University Press,2005
[9] Downey R G,Fellows M R．Parameterized Complexity[M]．New York:Springer,1999
[10] Roth-Korostensky C．Algothims for Building Multiple Sequence Alignments and Evolutionary Trees[D]．ETH Zurich,2000
[11] Stege U．Resolving Conflicts from Problems in Computational Biology[D]．ETH Zurich,2000
[12] Chen J,Kanj I A,Jia W．Vertex cover:further observations and further improvement[J]．Journal of Algorithms,2001,41:280-301
[13] Gottlob G,Scarcello F,Sideri M．Fixed-parameter complexity in AI and non-monotonic reasoning[J]．Artificial Intelligence,2002,138:55-86
[14] Scott J．Efficient algorithms for detecting signaling pathways in protein interaction networks[J]．Journal of Computational Bio-logy,2006,13:133-144
[15] Lindner C,Rothe J．Fixed-parameter tractability and parameterized complexity applied to problems from computational social choice[M]∥Holder A,ed．Mathematical Programming Glossary,1996
[16] Betzler N,Guo J,Niedermeier R．Parametefized computationalcomplexity of Dodgson and Young elections[J]．Information and Computation,2010,208(2):165-177
[17] Grohe M．The parameterized complexity of database queries[C]∥Paredaens J,Su Jian-wen,eds．Proc．of the 20th ACM Symp．on Principles of Database Systems．ACM Press New York．NY,USA,2001:82-92
[18] Wang J,Wang J,Chen J,et al．An automated signature generation spproach for polymorphic wornl based on color coding[C]∥Proceedings of IEEE International Conference on Communications．2009:1-6
[19] Nesetril J,Poljak S．On the complexity of the subgraph problem[C]∥Commentationes Mathematicae Universitatis Carolinae．1985,26:415-419
[20] Femau H．Edge dominating set:efficient enumeration-based exact algorithms[C]∥Bodlaender H L,Langston M,eds．Proc．of 2nd International Workshop on Parameterized and Exact Computation．Berlin:Springer-Verlag,2006:142-153
[21] Fernau H．Parameterized algorithms for hitting set:the weighted case[C]∥Calamoneri T,Finocchi I,1taliano G F,eds．Proc．of the 6^thItalian Conference on Algorithms and Complexity．Berlin:Springer-Vedag,2006:32-343
[22] Abu-Khzam F．Kernelization algorithms for d-hitting set problems[C]∥Dehne F K H A,Sack J-R,Zeh N,eds．Proc．of the 10th Workshop on Algorithms and Data Structures．Berlin:Spfinger-Verlag,2007:434-445
[23] Bousquet N,Daligault J,Thomasse S.Multicut is FPT[C]∥Proceeding STOC’ 11Proceedings of the 43rd Annual ACM Symposium on Theory of Computing．2011:459-468
[24] Downey R,Fellows M R．Fundamentals of Parameterized complexity[M]．Springer,2013
[25] Chen J,Friesen D,Jia W,et al．Using nondeteminism to design efficient determinilistic algorithms[J]．Algorithmica,2004,40:83-97
[26] Sloper C,Telle J A．An overview of techniques for designing parameterized algorithms[J]．Theory Computer Journal,2008,51:122-136
[27] Prieto E,Sloper C．Looking at the stars[J]．Theoretical Compu-ter Science,2006,351:437-445
[28] Huffner F,Niedermeier R,Wernicke S．Techniques for practical fixed-parameter algorithms[J]．The Computer Journal,2008,51(1):7-25
[29] 刘运龙．若干NP难解问题的参数化算法研究[D].长沙:中南大学,2009
[30] 李绍华,王建新,冯启龙,等．参数计算中核心化技术[J]．Journal of Software,2009,20(9):2307-2319
[31] Chen Jia-ner,Kanj I A,Xia Ge．Simplicity is Beauty:Improved Upper Bounds for Vertex cover.http://wenku.baidu.com/view/22ae88dbcezf0066f53322aa.html
[32] Abu-Khzam F N,Collins R L,Fellows M R,et al．Kernelizatin algorithms for the vertex cover problem:theory and experiments[C]∥Proceedings of Workshop on Algorithm Engineering and Experiments(ALENEX)．2004
[33] Nemhauser G L,Trotter L E．Vertex Packings:Structural pro-perties and algorithms[J]．Math．Programming,1975(8):232-248
[34] Fellows M．Blow-ups,win/win’s and crown rules:some new directions in FPT[C]∥LCNS 2880．Berlin:Springer-Verlag,2003:1-12
[35] Chlebfk M,Chlebikova J．Crown reductions for the MinimumWeighted Vertex cover problem[J]．Electronic Colloquium on Computational Complexity,2004,101
[36] Mathieson L,Prieto E,Shaw P．Packing edge disjoint triangles:A parameterized view[C]∥LNCS 3162．2004:127-137
[37] Ning D．Parameterized algorithm for the matching and packing problem [D]．Changsha:Central South University,2007
[38] Reed B,Smith K,Vetta A．Finding odd cycle transversals[C]∥Operation．Research．Letter,2004,32(4):299-301
[39] 王建新,江国红,李文军,等．反馈集问题的研究进展[J]．Computer Science,2011,38(1)
[40] Guo Jiong,Gramm J,Huffner F,et al．Improved fixed parameter algorithms for two feedback set problems [C]∥LNCS 3608,WADS 2005．Berlin:Springer,2005:158-168
[41] Dehne F,Fellows M,Langston M,et al．An fast fpt algorithmfor the undirected feedback vertex set problem[J]．Theory Computer System,2007,41(3):479-492
[42] Liu Y,Lu S,Chen J,et a1．Greedy localization and color-coding:improved matching and packing algorithms[C]∥Bodlaender H L,Langston M A．eds．Proc．of the 2nd International Workshop on Parameterized and Exact Computation．Berlin:Springer-Verlag,2006:84-95
[43] 冯启龙．packing和matching问题的参数算法研究 [D].长沙:中南大学,2010
[44] Alon N,Yuster R,Zwick U．Color-coding[J]．Journal of the ACM,1995,42:844-856
[45] 王建新,陈志彪,陈建二．最长路径问题研究进展[J]．计算机科学,2009,36(12)
[46] Robertson N,Seymour P D．Graph Minors．II．Algorithmc Aspects of Tree-width [J]．Journal of algoriths,1986,7(3):309-322
[47] 高文宇,李邵华．图的树分解及其算法应用研究进展．计算机科学,2012,39(3)
[48] Lu J H,Ling T B,Bao Z F,et al．Extended XML tree matching:theories and algorithms[J].IEEE Trans on knowledge and data engineering,2011,23(3):402-416

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed