Time, complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matching

Jun He, Xin Yao

Research output: Contribution to journalArticle

10 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)450-458
Number of pages9
JournalJournal of Computer Science and Technology
Volume19
Issue number4
DOIs
Publication statusPublished - 1 Jul 2004

Keywords

  • evolutionary algorithm (EA)
  • maximum matching
  • time complexity
  • combinatorial optimisation

Fingerprint

Dive into the research topics of 'Time, complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matching'. Together they form a unique fingerprint.

Cite this