We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 29 Issue 5
September  2014
Turn off MathJax
Article Contents
Abstract
References
Jianer Chen, Qi-Long Feng. On Unknown Small Subsets and Implicit Measures: New Techniques for Parameterized Algorithms[J]. Journal of Computer Science and Technology, 2014, 29(5): 870-878. DOI: 10.1007/s11390-014-1474-1
Citation: Jianer Chen, Qi-Long Feng. On Unknown Small Subsets and Implicit Measures: New Techniques for Parameterized Algorithms[J]. Journal of Computer Science and Technology, 2014, 29(5): 870-878. DOI: 10.1007/s11390-014-1474-1
shu

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

  • 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.

Funds: This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61173051, 61103033,
More Information
  • Author Bio:

    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.

  • Received Date: March 18, 2014
  • Revised Date: July 08, 2014
  • Published Date: September 04, 2014
    Abstract
  • 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.
    • FullText(HTML)
    • References (45)
  • [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.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (28) PDF downloads (1262) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return