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 20 Issue 1
January  2005
Turn off MathJax
Article Contents
Abstract
Related Articles
Jian-Er Chen. Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardnes[J]. Journal of Computer Science and Technology, 2005, 20(1).
Citation: Jian-Er Chen. Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardnes[J]. Journal of Computer Science and Technology, 2005, 20(1).
shu

Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardnes

More Information
  • Published Date: January 14, 2005
    Abstract
  • The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable. The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics. This survey gives an overview on the fundamentals, algorithms, techniques, and applications developed in the research of parameterized computation and complexity. We will also report the most recent advances and excitements, and discuss further research directions in the area.
    • FullText(HTML)
    • References (0)
    • Relative Articles

  • Related Articles

    [1]Jian-Xin Wang, Xiao-Shuang Xu, Jian-Er Chen. Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs[J]. Journal of Computer Science and Technology, 2008, 23(5): 763-768.
    [2]Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Th&oumlle, Henning Thomas. Approximation Algorithms for 3D Orthogonal Knapsack[J]. Journal of Computer Science and Technology, 2008, 23(5): 749-762.
    [3]Bing Yang, Jing Chen, En-Yue Lu, Si-Qing Zheng. Design and Performance Evaluation of Sequence Partition Algorithms[J]. Journal of Computer Science and Technology, 2008, 23(5): 711-718.
    [4]Ya-Feng Wu, Yin-Long Xu, Guo-Liang Chen. Approximation Algorithms for Steiner Connected Dominating Set[J]. Journal of Computer Science and Technology, 2005, 20(5): 713-716.
    [5]Yong Zhang, Hong Zhu. Approximation Algorithm for Weighted Weak Vertex Cover[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [6]Zi-Mao Li, Da-Ming Zhu, Shao-Han Ma. Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [7]HE Yong, CHEN Ting. A New Approximation Algorithm for Sorting of Signed Permutations[J]. Journal of Computer Science and Technology, 2003, 18(1).
    [8]ZHANG Li'ang, ZHANG Yin. Approximation for- Knapsack Problemswith Multiple Constraints[J]. Journal of Computer Science and Technology, 1999, 14(4): 289-297.
    [9]Huang Wenqi, Li Wei. A Hopeful CNF-SAT─Algorithm Its High Efficiency, Industrial Application and Limitation[J]. Journal of Computer Science and Technology, 1998, 13(1): 9-12.
    [10]Jiamg Xiong. Some Undecidable Problems on Approximability of NP Optimization Problems[J]. Journal of Computer Science and Technology, 1996, 11(2): 126-132.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (8) PDF downloads (1798) 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