We use cookies to improve your experience with our site.

Indexed in:

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

Submission System
(Author / Reviewer / Editor)
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).

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

More Information
  • Published Date: July 14, 2004
  • 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.
  • 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.

Catalog

    Article views (16) PDF downloads (1846) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return