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 19 Issue 4
July  2004
Turn off MathJax
Article Contents
Abstract
Related Articles
Jun He, Xin Yao. Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching[J]. Journal of Computer Science and Technology, 2004, 19(4).
Citation: Jun He, Xin Yao. Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching[J]. Journal of Computer Science and Technology, 2004, 19(4).
shu

Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching

More Information
  • Published Date: July 14, 2004
    Abstract
  • Most of works on the time complexity analysis of evolutionary algorithms have always focused on some artificial binary problems. The time complexity of the algorithms for combinatorial optimisation has not been well understood. This paper considers the time complexity of an evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximum cardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matching with nearly maximum cardinality in average polynomial time.
    • FullText(HTML)
    • References (0)
    • Relative Articles

  • Related Articles

    [1]Hua Jiang, Ke Bai, Hai-Jiao Liu, Chu-Min Li, Felip Manyà, Zhang-Hua Fu. Parallel Bounded Search for the Maximum Clique Problem[J]. Journal of Computer Science and Technology, 2023, 38(5): 1187-1202. DOI: 10.1007/s11390-022-1803-8
    [2]Wen-Ling Wu, Wen-Tao Zhang, Deng-Guo Feng. Impossible Differential Cryptanalysis of Reduced-Round ARIA and Camellia[J]. Journal of Computer Science and Technology, 2007, 22(3): 449-456.
    [3]JIANG Tao, LI Ming, Paul M.B. Average-Case Analysis of Algorithms Using Kolmogorov Complexity[J]. Journal of Computer Science and Technology, 2000, 15(5): 402-408.
    [4]MA Jun, MA Shaohan. An Efficient Parallel Graph Edge Matching Algorithmand Its Applications[J]. Journal of Computer Science and Technology, 1999, 14(2): 153-158.
    [5]GU Jun, GU Qianping, DU Dingzhu. On Optimizing the Satisfiability (SAT) Problem[J]. Journal of Computer Science and Technology, 1999, 14(1): 1-17.
    [6]Jiang Tianzi, Ma Songde. Contour Matching Using Wavelet Transform and Multigrid Methods[J]. Journal of Computer Science and Technology, 1997, 12(6): 564-570.
    [7]Gao Qingshi. A Unified O(log N) and Optimal Sorting Vector Algorithm[J]. Journal of Computer Science and Technology, 1995, 10(5): 470-475.
    [8]Tang Zhimin, Xia Peisu. A Maximum Time Difference Pipelined Arithmetic Unit Based on CMOS Gate Array[J]. Journal of Computer Science and Technology, 1995, 10(2): 97-103.
    [9]Wei Guoqing, Ma Songde. 3D Motion Estimation and Motion Fusion by Affine Region Matching[J]. Journal of Computer Science and Technology, 1993, 8(1): 17-25.
    [10]Lu Xuemiao. On the Complexity of Induction of Structural Descriptions[J]. Journal of Computer Science and Technology, 1987, 2(1): 12-21.
    • Supplements (0)

Catalog

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