Back to Search
Start Over
Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching.
- Source :
- Journal of Computer Science & Technology (10009000); July 2004, Vol. 19 Issue 4, p450-458, 9p
- Publication Year :
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
GRAPHIC methods
POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 10009000
- Volume :
- 19
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Journal of Computer Science & Technology (10009000)
- Publication Type :
- Academic Journal
- Accession number :
- 15081167