›› 2014, Vol. 29 ›› Issue (5): 870-878.doi: 10.1007/s11390-014-1474-1

Special Issue: Theory and Algorithms

• Theory and Algorithms • Previous Articles     Next Articles

On Unknown Small Subsets and Implicit Measures: New Techniques for Parameterized Algorithms

Jianer Chen1,2(陈建二), Member, ACM, Qi-Long Feng1, *(冯启龙)   

  1. 1. School of Information Science and Engineering, Central South University, Changsha 410083, China;
    2. Department of Computer Science, Texas A&M University, Texas 77843-3112, U. S. A.
  • Received:2014-03-19 Revised:2014-07-09 Online:2014-09-05 Published:2014-09-05
  • About author:Jianer Chen received the Ph.D. degree in computer science from Courant Institute of New York University in 1987 and the Ph.D. degree in mathematics from Columbia University in 1990. He is currently a professor of computer science at Texas A&M University, USA, and Central South University in Changsha, China. His main research is centered on computer algorithms and their applications. His current research projects include exact and parameterized algorithms, computer graphics, computer networks, and computational biology.
  • Supported by:

    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61173051, 61103033,

Parameterized computation is a recently proposed alternative approach to dealing with NP-hard problems. Developing efficient parameterized algorithms has become a very active research area in the current research in theoretical computer science. In this paper, we investigate a number of new algorithmic techniques that were proposed and initiated by ourselves in our research in parameterized computation. The techniques have proved to be very useful and promising, and have led to improved parameterized algorithms for many well-known NP-hard problems.

[1] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, W. H. Freeman and Company, 1979.

[2] Luo W, Wang J, Guo J, Chen J. Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks. Theoretical Computer Science, 2014, 518: 32-41.

[3] Wang J, Luo W, Feng Q, Guo J, Chen J. Improved linear problem kernel for planar connected dominating set. Theoretical Computer Science, 2013, 511: 2-12.

[4] Wang J, Luo W, Feng Q, Guo J. Parameterized complexity of Min-power multicast problems in wireless ad hoc networks. Theoretical Computer Science, 2013, 508: 16-25.

[5] Wang J, Tan P, Yao J, Feng Q, Chen J. On the minimum link-length rectilinear spanning path problem: Complexity and algorithms. IEEE Transactions on Computers, doi.ieeecomputersociety.org/10.1109/TC.2013.163, 2013 (preprint).

[6] Ausiello G, Crescenzi P, Gambosi G, Kann V, MarchettiSpaccamela A, Protasi M. Complexity and Approximation | Combinatorial Optimization Problems and Their Approximability Properties. Springer Verlag, 1999.

[7] Motwani R, Raghavan P. Randomized Algorithms. New York: Cambridge University Press, 1995.

[8] Michalewicz Z, Fogel D B. How to Solve It: Modern Heuristics. Berlin: Springer-Verlag, 2000.

[9] Roth-Korostensky C. Algorithms for building multiple sequence alignments and evolutionary trees [Ph.D. Thesis]. No. 13550, ETH Züich, 2000.

[10] Stege U. Resolving conflicts from problems in computational biology [Ph.D. Thesis]. No. 13364, ETH Zürich, 2000.

[11] Chen J, Kanj I A, Jia W. Vertex cover: Further observations and further improvements. In Proc. Workshop on GraphTheoretic Concepts in Computer Science-WG, Jun. 1999, pp.313-324.

[12] Chen J, Kanj I A, Xia G. Improved upper bounds for vertex cover. Theoretical Computer Science, 2010, 411(40/41/42): 3736-3756. 878 J. Comput. Sci. & Technol., Sept. 2014, Vol.29, No.5

[13] Cheetham J, Dehne F, Rau-Chaplin A, Stege U, Taillon P J. Solving large FPT problems on coarse-granined parallel machines. Journal of Computer and System Sciences, 2003, 67(4): 691-706.

[14] Lichtenstein O, Pnueli A. Checking that finite state concurrent programs satisfy their linear specification. In Proc. the 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Jan. 1985, pp.97-107.

[15] Henglein F, Mairson H G. The complexity of type inference for higher-order typed lambda calculi. Journal of Functional Programming, 1994, 4(4): 435-477.

[16] Chen J, Kanj I A. Constrained minimum vertex cover in bipartite graphs: Complexity and parameterized algorithms. Journal of Computer and System Sciences, 2003, 67(4): 833-847.

[17] Alon N, Yuster R, Zwick U. Color-coding. Journal of the ACM, 1995, 42(4): 844-856.

[18] Dorn F, Fomin F V, Thilikos D M. Subexponential parameterized algorithms. Computer Science Review, 2008, 2(1): 29-39.

[19] Downey R, Fellows M. Parameterized Complexity. New York: Springer-Verlag, 1999.

[20] Niedermeier R. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.

[21] Reed B, Smith K, Vetta A. Finding odd cycle transversals. Operations Research Letters, 2004, 32(4): 299-301.

[22] Kelley B P, Sharan R, Karp R M, Sittler T, Root D E, Stockwell B R, Ideker T. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci., 2003, 100(20): 11394-11399.

[23] Chen J, Kneis J, Lu S, Molle D, Richter S, Rossmanith P, Sze S H, Zhang F. Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM J. Comput., 2009, 38(6): 2526-2547.

[24] Chen J, Lu S. Improved parameterized set splitting algorithms: A probabilistic approach. Algorithmica, 2009, 54(4): 472-489.

[25] Kirkpatrick D G, Hell P. On the complexity of general graph factor problems. SIAM Journal on Computing, 1983, 12(3): 601-609.

[26] Feng Q, Wang J, Chen J. Matching and P2-Packing: Weighted versions. In Proc. the 17th COCOON, Aug. 2011, pp.343-353.

[27] Feng Q, Wang J, Chen J. Matching and weighted P2-Packing: Algorithms and kernels. Theoretical Computer Science, 2014, 522: 85-94.

[28] Feng Q, Wang J, Li S, Chen J. Random methods for parameterized problems. In Proc. the 19th COCOON, Jun. 2013, pp.89-100.

[29] Feng Q, Wang J, Li S, Chen J. Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems. Journal of Combinatorial Optimization, 2014. (to be appeared)

[30] Chen J, Lu S, Sze S H, Zhang F. Improved algorithms for path, matching, and packing problems. In Proc. the 18th Annual ACM-SIAM SODA, Jan. 2007, pp.298-307.

[31] Naor M, Schulman L, Srinivasan A. Splitters and near-optimal derandomization. In Proc. the 36th Annual Symposium on FOCS, Oct. 1995, pp.182-193.

[32] Kneis J, Mölle D, Richter S, Rossmanith P. Divide-and-color. In Proc. the 32nd Int. Workshop WG, Jun. 2006, pp.58-67.

[33] Chen J, Feng Q, Liu Y, Lu S, Wang J. Improved deterministic algorithms for weighted matching and packing problems. Theoretical Computer Science, 2011, 412(23): 2503-2512.

[34] Chen J, Liu Y, Lu S, Sze S H, Zhang F. Iterative expansion and color coding: An improved algorithm for 3D-matching. ACM Transactions on Algorithms, 2012, 8(1): Article No.6.

[35] Wang J, Feng Q, Chen J. An O(3:533k)-time parameterized algorithm for the 3-set packing problem. Theoretical Computer Science, 2011, 412(18): 1745-1753.

[36] Chen J, Fomin F, Liu Y, Lu S, Villanger Y. Improved algorithms for the feedback vertex set problems. Journal of Computer and System Sciences, 2008, 74(7): 1188-1198.

[37] Chen J, Liu Y, Lu S. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 2009, 55(11): 1-13.

[38] Chen J, Kanj I A. On approximating minimum vertex cover for graphs with perfect matching. Theoretical Computer Science, 2005, 337(1/2/3): 305-318.

[39] Mahajan M, Raman V. Parametrizing above guaranteed values: MaxSat and MaxCut. J. Algorithms, 1999, 31(2): 335-354.

[40] Mahajan M, Raman V, Sikdar S. Parameterizing MAX SNP problems above guaranteed values. In Proc. the 2nd Int. Workshop IWPEC, Sept. 2006, pp.38-49.

[41] Mahajan M, Raman V, Sikdar S. Parameterizing above or below guaranteed values. J. Comput. Syst. Sci., 2009, 75(2): 137-153.

[42] Razgon I, O'Sullivan B. Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences, 2009, 75(8): 435-450.

[43] Wang J, Li W, Li S, Chen J. On the parameterized vertex cover problem for graphs with perfect matching. Science China Information Sciences, 2014, 57(7): 1-12.

[44] Deming R. Independence numbers of graphs-An extension of the König-Egerváry theorem. Discrete Mathematics, 1979, 27(1): 23-33.

[45] Chen J, Liu Y, Lu S, O'Sullivan B, Razgon I. A fixedparameter algorithm for the directed feedback vertex set problem. Journal of the ACM, 2008, 55(5): Article No. 21.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Jin Zhiquan; Liu Chengfei; Sun Zhongxiu; Zhou Xiaofang; Chen Peipei; Gu Jianming;. Design and Implementation of a Heterogeneous Distributed Database System[J]. , 1990, 5(4): 363 -373 .
[2] Peter M. Haverty, Zhi-Ping Weng, and Ulla Hansen. Transcriptional Regulatory Networks Activated by PI3K and ERK Transduced Growth Signals in Human Glioblastoma Cells[J]. , 2005, 20(4): 439 -445 .
[3] Joonghyun Ryu, Rhohun Park, and Deok-Soo Kim. Connolly Surface on an Atomic Structure via Voronoi Diagram of Atoms[J]. , 2006, 21(2): 255 -260 .
[4] Yongxi Cheng. Generating Combinations by Three Basic Operations[J]. , 2007, 22(6): 909 -913 .
[5] Dilan Gõrür and Carl Edward Rasmussen. Dirichlet Process Gaussian Mixture Models: Choice of the Base Distribution[J]. , 2010, 25(4): 653 -664 .
[6] Bo Chen, Liang Liu, Hua-Dong Ma. CDM: Content Diffusion Model for Information-Centric Networks[J]. Journal of Computer Science and Technology, 2021, 36(6): 1431 -1451 .
[7] Mahsa Chitsaz, and Chaw Seng Woo, Member, IEEE. Software Agent with Reinforcement Learning Approach for Medical Image Segmentation[J]. , 2011, 26(2): 247 -255 .
[8] Wei-Wu Hu (胡伟武), Senior Member, CCF, Yan-Ping Gao (高燕萍), Member, CCF, Tian-Shi Chen (陈天石), and Jun-Hua Xiao (肖俊华), Member, CCF. The Godson Processors: Its Research, Development, and Contributions[J]. , 2011, 26(3): 363 -372 .
[9] Seleviawati Tarmizi, Prakash Veeraraghavan, and Somnath Ghosh. Improvement on the Multihop Shareholder Discovery for Threshold Secret Sharing in MANETs[J]. , 2011, 26(4): 711 -721 .
[10] Xiu-Li Ma (马秀莉), Hai-Feng Hu (胡海峰), Shuang-Feng Li (李双峰), Hong-Mei Xiao (肖红梅), Qiong Luo (罗琼), Dong-Qing Yang (杨冬青), Member,CCF, and Shi-Wei Tang (唐世渭), Senior Member, CCF. DHC: Distributed, Hierarchical Clustering in Sensor Networks[J]. , 2011, 26(4): 643 -662 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved