Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problem
Author: Shi, F.
Neumann, F.
Wang, J.
Citation: FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2019 / Friedrich, T., Doerr, C., Arnold, D.V. (ed./s), pp.133-146
Publisher: Association for Computing Machinery
Publisher Place: online
Issue Date: 2019
ISBN: 9781450362542
Conference Name: Foundations of Genetic Algorithms (FOGA) (27 Aug 2019 - 29 Aug 2019 : Potsdam, Germany)
Editor: Friedrich, T.
Doerr, C.
Arnold, D.V.
Statement of
Feng Shi, Frank Neumann, Jianxin Wang
Abstract: The Minimum Spanning Tree problem is a well-known combinatorial optimization problem, which has attracted much attention from the researchers in the field of evolutionary computing. Within the paper, a constrained version of the problem named Depth Restricted (1-2)-Minimum Spanning Tree problem is considered in the context of evolutionary algorithms, which had been shown to be NP-hard. We separately investigate the expected time (i.e., the expected number of fitness evaluations) of the (1+1) EA, the Multi-Objective Evolutionary Algorithm and its two variants adapted to the constrained version, to obtain an approximate solution with ratio 2 or 3/2 with respect to several different fitness functions. In addition, we observe a close connection between the constrained version and the Set Cover problem, and present a simple evolutionary algorithm for the 3-Set Cover problem. Based on the approximate solution returned by our evolutionary algorithm for the 3-Set Cover problem, an approximate solution with ratio better than 3/2 for the constrained version can be constructed.
Keywords: Minimum spanning tree
evolutionary algorithm
time analysis
depth restricted (1,2)-minimum spanning tree
Rights: © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
DOI: 10.1145/3299904.3340314
Grant ID:
Published version:
Appears in Collections:Aurora harvest 8
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.