Back to Search
Start Over
Performance analysis of evolutionary algorithm for the maximum internal spanning tree problem.
- Source :
-
Journal of Supercomputing . Jun2022, Vol. 78 Issue 9, p11949-11973. 25p. - Publication Year :
- 2022
-
Abstract
- The maximum internal spanning tree (MIST) problem is to find a spanning tree with maximum number of internal node for an undirected graph. It is a variation of the well-known minimum spanning tree problem and is NP-hard. Evolutionary algorithms (EAs) have been successfully applied to solve many NP-hard combinatorial optimization problems in numerical empirical studies. However, researchers know little about their performance guarantees from theory aspect. This paper designs a valid fitness function to guide the well-studied evolutionary algorithm, (1 + 1) EA , to optimize the MIST problem, and presents theoretical analysis to show that it can obtain a performance guarantee of 2 and 5/3 in expected runtime O (n m 2) and O (n m 4) , respectively. Moreover, this paper proves that the (1+1) EA can achieve a performance guarantee of 3 for a variation of the MIST problem, where each vertex is associated with a weight. In addition, comparison analyses on two family instance graphs are presented to show that (1 + 1) EA is better than two local search algorithms. This theoretical study provides insight into the process of (1 + 1) EA constructing a performance guarantee solution for the MIST problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09208542
- Volume :
- 78
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- Journal of Supercomputing
- Publication Type :
- Academic Journal
- Accession number :
- 156972774
- Full Text :
- https://doi.org/10.1007/s11227-022-04342-5