覆盖问题的参数算法研究
|
摘要
覆盖问题是计算几何和组合优化领域中的一类重要的难解问题,对此类问题的研究不但具有重大的理论意义,而且在生物计算、电路设计、网络选址、工艺流程分析等应用领域具有许多重要的实际意义。人们从实际应用中抽象出了许多的覆盖问题,如顶点覆盖问题、树覆盖问题、超平面覆盖问题、集合覆盖问题等。本文主要对超平面覆盖问题和基于保证值的完美匹配图中顶点覆盖问题进行了深入的研究。
对于超平面覆盖问题,本文首先通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,提出了一个时间复杂度为O*((0.736k)k)勺的确定性的参数算法,较大地改进了以前最好的时间复杂度为O*((k/2.2)2k)勺的算法。更一般地,我们还提出了关于超平面覆盖问题的确定性的参数算法,其时间复杂度为O*((dk)!/((d!)kk!)),较之前的时间复杂度为O*(kd(k+1))的算法亦有较大改进。
对于完美匹配图中基于保证值的顶点覆盖问题,已有相关文献提出了一个时间复杂度为O*(15k)勺的固定参数算法。本文对此算法作了进一步的改进,其整体思路是首先采用迭代压缩技术将原问题转化为求一个特殊的具有完美匹配的Konig图上的最小顶点覆盖问题,然后将后者进一步转化为参数化2-ASLASAT问题的一个变种问题(KPM-2-AASAT问题),最后,通过深入分析问题的结构特征,我们采用分枝搜索技术和隐含参数技术求解KPM-2-AASAT问题。整个算法的时间复杂度为O*(9勺,较之前最好结果有较大改进。
本文最后对上述两个问题的研究工作进行了总结,并对今后的相关研究工作做了简要的阐述。
Cover problem is a class of important fundamental problem in computational geometry and combinatorial optimization. Studying cover problems makes not only great theoretical significance but also much important practical significance in computational biology, circuit design, network address selection, process flow analysis, etc. There are many cover problems, abstracted from practical applications, such as Vertex Cover, Tree Cover, Hyperplane-Cover, Set Cover, etc. In this paper, we study the Hyperplane-Cover problem and the Above Guarantee Vertex Cover problem on graphs with perfect matching.
For the Hyperplane-Cover problem, a deterministic parameterized algorithm for the Line-Cover problem (a special case of Hyperplane-Cover problem) with running time O*((0.736k)k) is proposed firstly by further analyzing the structure of the problem, which significantly improves the previous best result O*((k/2.2)2k). Generally, a deterministic parameterized algorithm for the Hyperplane-Cover problem with running time O*((dk)!/((d!)kk!)) is given, which greatly improves the previous best result O*(kd(k+1)).
For the Above Guarantee Vertex Cover problem on graphs with perfect matching, there exists a fixed parameterized algorithm with running time O*(15k). We present an improved algorithm, the main idea of which is as follows. Firstly, we, using iterative compression technique, transform the PM-AGV-VC problem to a special Vertex Cover problem on Konig graph with perfect matching; later, we transform the latter to a variation of the parameterized 2-ASLASAT problem (KPM-2-AASAT problem); finally, through further analyzing the structure of the problem we, using branch and search method and implicit parameter technique, provide a parameterized algorithm for the KPM-2-AASAT problem. The total complexity of our algorithm is O*(9k), improving the previous best algorithm.
Finally, the study work on the problems, mentioned above, is summed up and some related future researches are proposed briefly.
对于超平面覆盖问题,本文首先通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,提出了一个时间复杂度为O*((0.736k)k)勺的确定性的参数算法,较大地改进了以前最好的时间复杂度为O*((k/2.2)2k)勺的算法。更一般地,我们还提出了关于超平面覆盖问题的确定性的参数算法,其时间复杂度为O*((dk)!/((d!)kk!)),较之前的时间复杂度为O*(kd(k+1))的算法亦有较大改进。
对于完美匹配图中基于保证值的顶点覆盖问题,已有相关文献提出了一个时间复杂度为O*(15k)勺的固定参数算法。本文对此算法作了进一步的改进,其整体思路是首先采用迭代压缩技术将原问题转化为求一个特殊的具有完美匹配的Konig图上的最小顶点覆盖问题,然后将后者进一步转化为参数化2-ASLASAT问题的一个变种问题(KPM-2-AASAT问题),最后,通过深入分析问题的结构特征,我们采用分枝搜索技术和隐含参数技术求解KPM-2-AASAT问题。整个算法的时间复杂度为O*(9勺,较之前最好结果有较大改进。
本文最后对上述两个问题的研究工作进行了总结,并对今后的相关研究工作做了简要的阐述。
Cover problem is a class of important fundamental problem in computational geometry and combinatorial optimization. Studying cover problems makes not only great theoretical significance but also much important practical significance in computational biology, circuit design, network address selection, process flow analysis, etc. There are many cover problems, abstracted from practical applications, such as Vertex Cover, Tree Cover, Hyperplane-Cover, Set Cover, etc. In this paper, we study the Hyperplane-Cover problem and the Above Guarantee Vertex Cover problem on graphs with perfect matching.
For the Hyperplane-Cover problem, a deterministic parameterized algorithm for the Line-Cover problem (a special case of Hyperplane-Cover problem) with running time O*((0.736k)k) is proposed firstly by further analyzing the structure of the problem, which significantly improves the previous best result O*((k/2.2)2k). Generally, a deterministic parameterized algorithm for the Hyperplane-Cover problem with running time O*((dk)!/((d!)kk!)) is given, which greatly improves the previous best result O*(kd(k+1)).
For the Above Guarantee Vertex Cover problem on graphs with perfect matching, there exists a fixed parameterized algorithm with running time O*(15k). We present an improved algorithm, the main idea of which is as follows. Firstly, we, using iterative compression technique, transform the PM-AGV-VC problem to a special Vertex Cover problem on Konig graph with perfect matching; later, we transform the latter to a variation of the parameterized 2-ASLASAT problem (KPM-2-AASAT problem); finally, through further analyzing the structure of the problem we, using branch and search method and implicit parameter technique, provide a parameterized algorithm for the KPM-2-AASAT problem. The total complexity of our algorithm is O*(9k), improving the previous best algorithm.
Finally, the study work on the problems, mentioned above, is summed up and some related future researches are proposed briefly.
引文
[1]M. R. Garey and D. S. Johnson, Computers, and Intractability:A Guide to the Thoery of NP-completeness, W. H. Freeman and Company, New York,1979.
[2]Pearl, Judea. Heuristics. Addison-Wesley Pub,1984.
[3]Z. Michalewicz, D. B.Fogel. How to Solve It:Modern Heuristics. Springer-Verlag,2000.
[4]G.Ausiello, P.Cresenzi, G.Gambosi, et al. Complexity and Approximation. Springer-Verlag,1999.
[5]D. S. Hochbaum (ed.). Approximation algorithms for NP-hard problems. Boston, MA:PWS Publishing Company,1997.
[6]R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
[7]M. Mitzenmacher, E. Upfal. Probability and Computing:Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY),2005.
[8]R. G.. Downey and M. R. Fellows, Parameterized Complexity, New York, New York:Springer,1999.
[9]J. Alber, H. Fernau, and R. Niedermeier, Parameterized complexity:exponential speed-up for planar graph problems, Lecture Notes in Computer Science 2076 (ICALP'01), (2001), pp.261-272.
[10]M. Grohe, The parameterized complexity of database queries, Proc.20th ACM Symp. on Principles of Database Systems (PODS'01), (2001), pp.82-92.
[11]J. Chen and I. Kanj, On constrained minimum vertex covers of bipartite graphs: improved algorithms, Lecture Notes in Computer Science 2204 (WG'01), (2001), pp.55-65.
[12]H. Bodlaender, M. Fellows, M. Hallett, and H. Wareham, Parameterized complexity analysis in computational biology, Computer Applications in the Biosciences 11, (1995), pp.49-57.
[13]H. Bodlaender, M. Fellows, M. Hallett, and H. Wareham, The parameterized complexity of the longest common subsequence problem, Theoretical Computer Science 147, (1995), pp.31-54.
[14]G. Gottlob, F. Scarcello, M. Sideri, Fixed-parameter complexity in AI and nonmonotonic reasoning, Artificial Intelligence 138, (2002), pp.55-86.
[15]R. Downey, M. Fellows, A. Vardy, and G. Whittle, The parameterized
complexity of some fundamental problems in coding theory, SIAM J. Computing 29, (1999), pp.545-570.
[16]G. Gonnet, M. Hallett, C. Korostensky, and L. Bernardin. Darwin v.2.0:an interpreted computer language for the biosciences. Bioinformatics 16, (2000), pp. 101-103.
[17]C. Papadimitriou and M. Yannakakis, On the complexity of database queries, Journal of Computer and System Sciences 58, (1999), pp.407-427
[18]J. Chen. Parameterized Computation and Complexity:A New Approach Dealing with NP-Hardness. Journal of computer science and technology,2005,20(1): 18-37.
[19]J. Chen, I. Kanj, J. Meng, G. Xia, and F. Zhang. On the effective enumerability of NP problems. In:Bodlaender H L, Langston M A, eds. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), Lecture Notes in Computer Science 4169. Springer-Verlag,2006.215-226.
[20]R. Niedermeier, P. Rossmanith. An efficient fixed parameter algorithm for 3-Hitting Set. Journal of Discrete Algorithms,2002,2(1):93-107.
[21]R. Niedermeier, P. Rossmanith. On efficient fixed parameter algorithms for weighted vertex cover. Journal of Algorithms,2003,47(2):63-77.
[22]王建新,黄元南,陈建二.一种基于彩色编码的基序发现算法.软件学报,2007,18(6)：1298-1307.
[23]王建新,刘云龙,陈建二.一种在元素与颜色规模相近时的有效着色算法及其应用.计算机学报,2008,31(1)：32-42.
[24]R. Niedermeier, P.Rossmanith. A general method to speed up fixed parameter tractable algorithms. Information Processing Letters,2000,73:125-129.
[25]J. M. Robson. Algorithms for maximum independent sets. J.Algorithms,1986,7: 425-440.
[26]G.Woeginger. Exact algorithms for NP-hard problems:a survey. Lecture Notes in Computer Science,2001,2570:185-207.
[27]李绍华王建新冯启龙陈建二. 参数计算中核心化技术及其应用的研究进展软件学报.200920(9).
[28]N. Faisal, Abu-Khzam, R.L. Collins, M.R. Fellows, M. Langston, W.H. Suters, C.T.Symons. Kernelization algorithms for the vertex cover problem:theory and experiments. ALENEX/ANALC 2004, pp.62-69.
[29]J. Alber, M. R. Fellows, R. Niedermeier. Efficient data reducation for dominating set:a linear problem kernel for the planar case. In:Martti Penttonen, Erik Mei neche Schmidt, eds. Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Berlin:Springer-Verlag,2002,150-159.
[30]F. Huffner, R. Niedermeier, S. Wernicke. Techniques for practical fixed-parameter algorithms. The Computer Journal,2008,51(1):7-25.
[31]F. Dehne, M. Fellows, F. Rosamond, P. Shaw. Greedy Localization, Iterative Compression and Modeled Crown Reductions:New FPT Techniques and Improved Algorithms for Max Set Splitting and Vertex Cover, LNCS 3162, page 271-281,2004.
[32]M. Fellows. Blow-ups, win/win's, and crown rules:some new directions in FPT. LCNS, Vol.2880, Springer, Berlin, pp.1-12,2003.
[33]E. Prieto. The Method of Extremal Structure on the k-Maximum Cut Problem. Proc. Computing:The Australasian Theory Symposium (CATS 2005). Conferences in Research and Practice in Information Technology,2005, vol.41, pages 119-126.
[34]B. Reed, K. Smith, and A. Vetta. Finding Odd Cycle Transversals, Operations Research Letters,32, pages 299-301,2003.
[35]F. Dehne, M. Fellows, F. Rosamond, P. Shaw. Greedy Localization, terative Compression and Modeled Crown Reductions:New FPT Techniques nd Improved Algorithms for Max Set Splitting and Vertex Cover, roceedings of IWPEC04, LNCS 3162, pages 271-281,2004.
[36]M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, J.A.Telle, Finding k disjoint triangles in an arbitrary graph. To appear in proceedings 30th Workshop on Graph Theoretic Concepts in Computer Science (WG'04), Springer Lecture Notes in Computer Science, (2004).
[37]N. Robertson, PD. Seymour. Graph Minors XX Wagner's conjecture. Journal of Combinatorial Theory Series B. Volume 92, Issue 2 (November 2004).
[38]E. Demaine and M. Hajiaghayi. Bidimensionality:New Connections between FPT Algorithms and PTASs, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), January 23-25, pages 590-601,2005.
[39]J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, vol.33, pages 461-493,2002.
[40]J. Chen. Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters. In:E. Demaine, G. Z. Gutin, D. Marx, U. Stege, eds. Proceedings of the 3rd International Workshop on Parameterized and Exact Computation. Berlin: Springer-Verlag,2008,1-8.
[41]J. Chen, and S. Lu. Improved parameterized set splitting algorithms:a probabilistic approach. Algorithmica, accepted,2008
[42]J. Chen, I. Kanj and G. Xia. Improved Parameterized Upper Bounds for Vertex Cover. MFCS 2006.
[43]J. Chen, F. Fomin, Y. Liu, S. Lu and Y. Villanger. Improved Algorithms for the Feedback Vertex Set Problems. WADS 2007.
[44]J. Nederlof, Fast polynomial-space algorithms using Mobius inversion: Improving on Steiner Tree and related problems, (2009).
[45]Fedor V. Fomin, Dimitrios M. Thilikos:Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up. SIAM J. Comput.36(2):281-309 (2006).
[46]S. Bocker, S. Briesemeister, Q. Bui and Anke TruB. PEACE:Parameterized and Exact Algorithms for Cluster Editing. Manuscript, Lehrstuhl fur Bioinformatik, Friedrich-Schiller-Universitat Jena,2007.
[47]R. Williams, Finding Paths of Length k in O*(2k) Time, Inform. Process. Letters, 109(6):315-318, (2009).
[48]J. Chen, I. A. Kanj, W. Jia. Vertex cover:Further observations and further improvements. Journal of Algorithms,41:280-301,2001
[49]Faisal N. Abu-Khzam. Kernelization Algorithms for d-Hitting Set Problems, WADS 2007.
[50]E. Prieto. The Method of Extremal Structure on the k-MAXIMUM CUT Problem. Proceedings of Computing:Australian Computer Science Communications, vol. 27(4), pages 119-126,2005.
[51]J. Alber, M. Fellows, and R. Niedermeier. Polynomial time data reduction for dominating set. Joural of the ACM 51, pp.363-384.
[52]J. Chen, H. Fernau, et al. Parametric Duality and Kernelization:Lower Bounds and Upper Bounds on Kernel Size. STACS 2005:269-280.
[53]Niedermeier, R. Invitation to Fixed Parameter Algorithms. Oxford University Press,2006.
[54]Jianxin Wang, Dan Ning, Qiliong Feng and Jianer Chen. An Improved Parameterized Algorithm for a Generalized Matching Problem. Proc.5th Annual Conference on Theory and Applications of Models of Computation (TAMC2008), pp:212-222,2008.
[55]Jiong Guo. A More Effective Linear Kernelization for Cluster Editting. LNCS 4614, PP.36047,2007.
[56]S. Langerman and P. Morin. Covering Things with Things. Proc.10th Annual Europ. Symp. on Algorithms (Rome, Italy), LNCS 2461:662-673. Springer Verlag, Heidelberg, Germany,2002.
[57]Jens Gramm. Jiong Guo, Falk Huffner, Rolf Niedermeier. Data reduction, exact, and heuristic algorithms for Clique Cover. In Proc.8th ACM-SIAM ALENEX, pages 86-94. ACM-SIAM,2006.
[58]Egbert Mujuni, Frances Rosamond. Parameterized Complexity of the Clique Partition Problem. CATS2008,Wollongong, NSW, Australia,2008.
[59]P. Bonsma and Florian Zickfeld. Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. LATIN 2008:531-543.
[60]N. Bousquet, J. Daligault, S. Thomass'e, and A. Yeo. A polynomial kernel for multicut in trees. In S. Albers and J. Y. Marion, editors, Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, volume 09001 of Dagstuhl Seminar Proceedings, pages 183-194, Schloss Dagstuhl, Germany,2009. Leibniz-Zentrum fuer Informatik.
[61]S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomass'e. Kernels for feedback arc set in tournaments. The Computing Research Repository, abs/0907.2165,2009.
[62]J. Chen, I. Kanj, J. Meng, Xia G, and F. Zhang. On the effective enumerability of NP problems. In:Bodlaender H L, Langston M A, eds. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), Lecture Notes in Computer Science 4169. Springer-Verlag,2006.215-226.
[63]Jianxin Wang, Guohong Jiang. A fixed-parameter enumeration algorithm for the weighted FVS problem. TAMC 09.
[64]Jianxin Wang, Beiwei Chen, Qilong Feng, Jianer Chen. An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set Problem. FAW2009.
[65]M. Grantson and C. Levcopoulos. Covering a Set of Points with a Minimum Number of Lines. EWCG 2006, Delphi, March 27-29,2006.
[66]J. Chen and I. A. Kanj. On Approximating Minimum Vertex Cover for Graphs
with Perfect Matching. Theoretical Computer Science Vol 337, pp.305-318, 2005.
[67]Igor Razgon, Barry O'Sullivan. Almost 2-SAT is Fixed-Parameter Tractable. Springer Berlin/Heidelberg 2008,551-562.
[68]N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters,1:194-197,1982.
[69]V. Kumar, S. Arya, and H. Ramesh. Hardness of Set Cover With Intersection 1. Proc.27th Int. Coll. Automata, Languages and Programming, LNCS 1853:624-635. Springer-Verlag, Heidelberg, Germany 2000.
[70]Franco P. Preparata and Michael Ian Shamos. Computational Geometry:An Introduction. Springer-Verlag,1985.
[71]J. F. Buss and J. Goldsmith, Nondeterminism within P, SIAM Journal on Computing 22, (1993), pp.560-572.
[72]R. G. Downey and M. R. Fellows, Parameterized computational feasibility, in Feasible Mathematics Ⅱ, P. Clote and J. Remmel, eds., Boston, Birkhauser (1995), pp.219-244.
[73]R. Balasubramanian, M. R. Fellows, and V. Raman, An improved fixed parameter algorithm for vertex cover, Information Processing Letters 65, (1998), pp.163-168.
[74]R. G. Downey, M. R. Fellows, and U. Stege, Parameterized complexity:A framework for systematically confronting computational intractability, in Contemporary Trends in Discrete Mathematics:From DIMACS and DIMATIA to the Future, F. Roberts, J. Kratochvil, and J. Nesetril, eds., AMS-DIMACS Proceedings Series 49, AMS, (1999), pp.49-99.
[75]R. Niedermeier and P. Rossmanith, Upper bounds for vertex cover further improved, Lecture Notes in Computer Science 1563 (STACS'99), (1999), pp. 561-570.
[76]U. Stege and M. Fellows, An improved fixed-parameter-tractable algorithm for vertex cover, Technical Report 318, Department of Computer Science, ETH Zurich, April 1999.
[77]S. Mishra, V. Raman, S. Saurabh, S. Sikdar, and C. R. Subramanian. The complexity of finding subgraphs whose matching number equals the vertex cover number. In Proceedings 18th International Symposium on Algorithms and Computation, ISAAC 2007, pages 268-279. Springer Verlag, Lecture Notes in
Computer Science, vol.4835,2007.
[78]Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji. Approximated Vertex Cover for Graphs with Perfect Matchings. Transactions on Information and Systems, Volume E89-D, Issue 8 (August 2006).
[79]Meena Mahajan, Venkatesh Raman, Somnath Sikdar. Parameterizing above or below guaranteed values. Journal of Computer and System Sciences 75 (2009) 137-153.
[80]M. Mahajan, V. Raman. Parameterizing above guaranteed values:MaxSat and MaxCut. Journal of Algorithms 1999,31(2):335-354.
[81]L. Yunlong. Research on Parameterized Algorithms for Several NP-hard Problems. A Thesis Submitted for The Degree of Doctor of Philosophy. Central South University of China. December 2009.
[82]V. Raman, S. Saurabh. Improved fixed parameter tractable algorithms for two edge problems:MAXCUT and MAXDAG. Information Processing letters, 2007,104(2):65-72.
[83]G. Gutin, A. Rafiey, S. Szeider, et al. The Linear Arrangement Problem Parameterized Above Guaranteed Value. Lecture Notes in Computer Science, (CIAC'06),2006,3998:356-367.
[2]Pearl, Judea. Heuristics. Addison-Wesley Pub,1984.
[3]Z. Michalewicz, D. B.Fogel. How to Solve It:Modern Heuristics. Springer-Verlag,2000.
[4]G.Ausiello, P.Cresenzi, G.Gambosi, et al. Complexity and Approximation. Springer-Verlag,1999.
[5]D. S. Hochbaum (ed.). Approximation algorithms for NP-hard problems. Boston, MA:PWS Publishing Company,1997.
[6]R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
[7]M. Mitzenmacher, E. Upfal. Probability and Computing:Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY),2005.
[8]R. G.. Downey and M. R. Fellows, Parameterized Complexity, New York, New York:Springer,1999.
[9]J. Alber, H. Fernau, and R. Niedermeier, Parameterized complexity:exponential speed-up for planar graph problems, Lecture Notes in Computer Science 2076 (ICALP'01), (2001), pp.261-272.
[10]M. Grohe, The parameterized complexity of database queries, Proc.20th ACM Symp. on Principles of Database Systems (PODS'01), (2001), pp.82-92.
[11]J. Chen and I. Kanj, On constrained minimum vertex covers of bipartite graphs: improved algorithms, Lecture Notes in Computer Science 2204 (WG'01), (2001), pp.55-65.
[12]H. Bodlaender, M. Fellows, M. Hallett, and H. Wareham, Parameterized complexity analysis in computational biology, Computer Applications in the Biosciences 11, (1995), pp.49-57.
[13]H. Bodlaender, M. Fellows, M. Hallett, and H. Wareham, The parameterized complexity of the longest common subsequence problem, Theoretical Computer Science 147, (1995), pp.31-54.
[14]G. Gottlob, F. Scarcello, M. Sideri, Fixed-parameter complexity in AI and nonmonotonic reasoning, Artificial Intelligence 138, (2002), pp.55-86.
[15]R. Downey, M. Fellows, A. Vardy, and G. Whittle, The parameterized
complexity of some fundamental problems in coding theory, SIAM J. Computing 29, (1999), pp.545-570.
[16]G. Gonnet, M. Hallett, C. Korostensky, and L. Bernardin. Darwin v.2.0:an interpreted computer language for the biosciences. Bioinformatics 16, (2000), pp. 101-103.
[17]C. Papadimitriou and M. Yannakakis, On the complexity of database queries, Journal of Computer and System Sciences 58, (1999), pp.407-427
[18]J. Chen. Parameterized Computation and Complexity:A New Approach Dealing with NP-Hardness. Journal of computer science and technology,2005,20(1): 18-37.
[19]J. Chen, I. Kanj, J. Meng, G. Xia, and F. Zhang. On the effective enumerability of NP problems. In:Bodlaender H L, Langston M A, eds. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), Lecture Notes in Computer Science 4169. Springer-Verlag,2006.215-226.
[20]R. Niedermeier, P. Rossmanith. An efficient fixed parameter algorithm for 3-Hitting Set. Journal of Discrete Algorithms,2002,2(1):93-107.
[21]R. Niedermeier, P. Rossmanith. On efficient fixed parameter algorithms for weighted vertex cover. Journal of Algorithms,2003,47(2):63-77.
[22]王建新,黄元南,陈建二.一种基于彩色编码的基序发现算法.软件学报,2007,18(6)：1298-1307.
[23]王建新,刘云龙,陈建二.一种在元素与颜色规模相近时的有效着色算法及其应用.计算机学报,2008,31(1)：32-42.
[24]R. Niedermeier, P.Rossmanith. A general method to speed up fixed parameter tractable algorithms. Information Processing Letters,2000,73:125-129.
[25]J. M. Robson. Algorithms for maximum independent sets. J.Algorithms,1986,7: 425-440.
[26]G.Woeginger. Exact algorithms for NP-hard problems:a survey. Lecture Notes in Computer Science,2001,2570:185-207.
[27]李绍华王建新冯启龙陈建二. 参数计算中核心化技术及其应用的研究进展软件学报.200920(9).
[28]N. Faisal, Abu-Khzam, R.L. Collins, M.R. Fellows, M. Langston, W.H. Suters, C.T.Symons. Kernelization algorithms for the vertex cover problem:theory and experiments. ALENEX/ANALC 2004, pp.62-69.
[29]J. Alber, M. R. Fellows, R. Niedermeier. Efficient data reducation for dominating set:a linear problem kernel for the planar case. In:Martti Penttonen, Erik Mei neche Schmidt, eds. Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Berlin:Springer-Verlag,2002,150-159.
[30]F. Huffner, R. Niedermeier, S. Wernicke. Techniques for practical fixed-parameter algorithms. The Computer Journal,2008,51(1):7-25.
[31]F. Dehne, M. Fellows, F. Rosamond, P. Shaw. Greedy Localization, Iterative Compression and Modeled Crown Reductions:New FPT Techniques and Improved Algorithms for Max Set Splitting and Vertex Cover, LNCS 3162, page 271-281,2004.
[32]M. Fellows. Blow-ups, win/win's, and crown rules:some new directions in FPT. LCNS, Vol.2880, Springer, Berlin, pp.1-12,2003.
[33]E. Prieto. The Method of Extremal Structure on the k-Maximum Cut Problem. Proc. Computing:The Australasian Theory Symposium (CATS 2005). Conferences in Research and Practice in Information Technology,2005, vol.41, pages 119-126.
[34]B. Reed, K. Smith, and A. Vetta. Finding Odd Cycle Transversals, Operations Research Letters,32, pages 299-301,2003.
[35]F. Dehne, M. Fellows, F. Rosamond, P. Shaw. Greedy Localization, terative Compression and Modeled Crown Reductions:New FPT Techniques nd Improved Algorithms for Max Set Splitting and Vertex Cover, roceedings of IWPEC04, LNCS 3162, pages 271-281,2004.
[36]M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, J.A.Telle, Finding k disjoint triangles in an arbitrary graph. To appear in proceedings 30th Workshop on Graph Theoretic Concepts in Computer Science (WG'04), Springer Lecture Notes in Computer Science, (2004).
[37]N. Robertson, PD. Seymour. Graph Minors XX Wagner's conjecture. Journal of Combinatorial Theory Series B. Volume 92, Issue 2 (November 2004).
[38]E. Demaine and M. Hajiaghayi. Bidimensionality:New Connections between FPT Algorithms and PTASs, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), January 23-25, pages 590-601,2005.
[39]J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, vol.33, pages 461-493,2002.
[40]J. Chen. Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters. In:E. Demaine, G. Z. Gutin, D. Marx, U. Stege, eds. Proceedings of the 3rd International Workshop on Parameterized and Exact Computation. Berlin: Springer-Verlag,2008,1-8.
[41]J. Chen, and S. Lu. Improved parameterized set splitting algorithms:a probabilistic approach. Algorithmica, accepted,2008
[42]J. Chen, I. Kanj and G. Xia. Improved Parameterized Upper Bounds for Vertex Cover. MFCS 2006.
[43]J. Chen, F. Fomin, Y. Liu, S. Lu and Y. Villanger. Improved Algorithms for the Feedback Vertex Set Problems. WADS 2007.
[44]J. Nederlof, Fast polynomial-space algorithms using Mobius inversion: Improving on Steiner Tree and related problems, (2009).
[45]Fedor V. Fomin, Dimitrios M. Thilikos:Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up. SIAM J. Comput.36(2):281-309 (2006).
[46]S. Bocker, S. Briesemeister, Q. Bui and Anke TruB. PEACE:Parameterized and Exact Algorithms for Cluster Editing. Manuscript, Lehrstuhl fur Bioinformatik, Friedrich-Schiller-Universitat Jena,2007.
[47]R. Williams, Finding Paths of Length k in O*(2k) Time, Inform. Process. Letters, 109(6):315-318, (2009).
[48]J. Chen, I. A. Kanj, W. Jia. Vertex cover:Further observations and further improvements. Journal of Algorithms,41:280-301,2001
[49]Faisal N. Abu-Khzam. Kernelization Algorithms for d-Hitting Set Problems, WADS 2007.
[50]E. Prieto. The Method of Extremal Structure on the k-MAXIMUM CUT Problem. Proceedings of Computing:Australian Computer Science Communications, vol. 27(4), pages 119-126,2005.
[51]J. Alber, M. Fellows, and R. Niedermeier. Polynomial time data reduction for dominating set. Joural of the ACM 51, pp.363-384.
[52]J. Chen, H. Fernau, et al. Parametric Duality and Kernelization:Lower Bounds and Upper Bounds on Kernel Size. STACS 2005:269-280.
[53]Niedermeier, R. Invitation to Fixed Parameter Algorithms. Oxford University Press,2006.
[54]Jianxin Wang, Dan Ning, Qiliong Feng and Jianer Chen. An Improved Parameterized Algorithm for a Generalized Matching Problem. Proc.5th Annual Conference on Theory and Applications of Models of Computation (TAMC2008), pp:212-222,2008.
[55]Jiong Guo. A More Effective Linear Kernelization for Cluster Editting. LNCS 4614, PP.36047,2007.
[56]S. Langerman and P. Morin. Covering Things with Things. Proc.10th Annual Europ. Symp. on Algorithms (Rome, Italy), LNCS 2461:662-673. Springer Verlag, Heidelberg, Germany,2002.
[57]Jens Gramm. Jiong Guo, Falk Huffner, Rolf Niedermeier. Data reduction, exact, and heuristic algorithms for Clique Cover. In Proc.8th ACM-SIAM ALENEX, pages 86-94. ACM-SIAM,2006.
[58]Egbert Mujuni, Frances Rosamond. Parameterized Complexity of the Clique Partition Problem. CATS2008,Wollongong, NSW, Australia,2008.
[59]P. Bonsma and Florian Zickfeld. Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. LATIN 2008:531-543.
[60]N. Bousquet, J. Daligault, S. Thomass'e, and A. Yeo. A polynomial kernel for multicut in trees. In S. Albers and J. Y. Marion, editors, Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, volume 09001 of Dagstuhl Seminar Proceedings, pages 183-194, Schloss Dagstuhl, Germany,2009. Leibniz-Zentrum fuer Informatik.
[61]S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomass'e. Kernels for feedback arc set in tournaments. The Computing Research Repository, abs/0907.2165,2009.
[62]J. Chen, I. Kanj, J. Meng, Xia G, and F. Zhang. On the effective enumerability of NP problems. In:Bodlaender H L, Langston M A, eds. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), Lecture Notes in Computer Science 4169. Springer-Verlag,2006.215-226.
[63]Jianxin Wang, Guohong Jiang. A fixed-parameter enumeration algorithm for the weighted FVS problem. TAMC 09.
[64]Jianxin Wang, Beiwei Chen, Qilong Feng, Jianer Chen. An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set Problem. FAW2009.
[65]M. Grantson and C. Levcopoulos. Covering a Set of Points with a Minimum Number of Lines. EWCG 2006, Delphi, March 27-29,2006.
[66]J. Chen and I. A. Kanj. On Approximating Minimum Vertex Cover for Graphs
with Perfect Matching. Theoretical Computer Science Vol 337, pp.305-318, 2005.
[67]Igor Razgon, Barry O'Sullivan. Almost 2-SAT is Fixed-Parameter Tractable. Springer Berlin/Heidelberg 2008,551-562.
[68]N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters,1:194-197,1982.
[69]V. Kumar, S. Arya, and H. Ramesh. Hardness of Set Cover With Intersection 1. Proc.27th Int. Coll. Automata, Languages and Programming, LNCS 1853:624-635. Springer-Verlag, Heidelberg, Germany 2000.
[70]Franco P. Preparata and Michael Ian Shamos. Computational Geometry:An Introduction. Springer-Verlag,1985.
[71]J. F. Buss and J. Goldsmith, Nondeterminism within P, SIAM Journal on Computing 22, (1993), pp.560-572.
[72]R. G. Downey and M. R. Fellows, Parameterized computational feasibility, in Feasible Mathematics Ⅱ, P. Clote and J. Remmel, eds., Boston, Birkhauser (1995), pp.219-244.
[73]R. Balasubramanian, M. R. Fellows, and V. Raman, An improved fixed parameter algorithm for vertex cover, Information Processing Letters 65, (1998), pp.163-168.
[74]R. G. Downey, M. R. Fellows, and U. Stege, Parameterized complexity:A framework for systematically confronting computational intractability, in Contemporary Trends in Discrete Mathematics:From DIMACS and DIMATIA to the Future, F. Roberts, J. Kratochvil, and J. Nesetril, eds., AMS-DIMACS Proceedings Series 49, AMS, (1999), pp.49-99.
[75]R. Niedermeier and P. Rossmanith, Upper bounds for vertex cover further improved, Lecture Notes in Computer Science 1563 (STACS'99), (1999), pp. 561-570.
[76]U. Stege and M. Fellows, An improved fixed-parameter-tractable algorithm for vertex cover, Technical Report 318, Department of Computer Science, ETH Zurich, April 1999.
[77]S. Mishra, V. Raman, S. Saurabh, S. Sikdar, and C. R. Subramanian. The complexity of finding subgraphs whose matching number equals the vertex cover number. In Proceedings 18th International Symposium on Algorithms and Computation, ISAAC 2007, pages 268-279. Springer Verlag, Lecture Notes in
Computer Science, vol.4835,2007.
[78]Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji. Approximated Vertex Cover for Graphs with Perfect Matchings. Transactions on Information and Systems, Volume E89-D, Issue 8 (August 2006).
[79]Meena Mahajan, Venkatesh Raman, Somnath Sikdar. Parameterizing above or below guaranteed values. Journal of Computer and System Sciences 75 (2009) 137-153.
[80]M. Mahajan, V. Raman. Parameterizing above guaranteed values:MaxSat and MaxCut. Journal of Algorithms 1999,31(2):335-354.
[81]L. Yunlong. Research on Parameterized Algorithms for Several NP-hard Problems. A Thesis Submitted for The Degree of Doctor of Philosophy. Central South University of China. December 2009.
[82]V. Raman, S. Saurabh. Improved fixed parameter tractable algorithms for two edge problems:MAXCUT and MAXDAG. Information Processing letters, 2007,104(2):65-72.
[83]G. Gutin, A. Rafiey, S. Szeider, et al. The Linear Arrangement Problem Parameterized Above Guaranteed Value. Lecture Notes in Computer Science, (CIAC'06),2006,3998:356-367.