Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Improving local search in a minimum vertex cover solver for classes of networks
Author: Wagner, M.
Friedrich, T.
Lindauer, M.
Citation: Proceedings of the Institution of Civil Engineers: Civil Engineering, 2017, pp.1704-1711
Publisher: IEEE
Issue Date: 2017
Series/Report no.: IEEE Congress on Evolutionary Computation
ISBN: 9781509046027
ISSN: 0965-089X
Conference Name: IEEE Congress on Evolutionary Computation (CEC 2017) (5 Jun 2017 - 8 Jun 2017 : San Sebastián, SPAIN)
Statement of
Markus Wagner, Tobias Friedrich and Marius Lindauer
Abstract: For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks—which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.
Rights: ©2017 IEEE
DOI: 10.1109/CEC.2017.7969507
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.