Improving local search in a minimum vertex cover solver for classes of networks

verfasst von

Markus Wagner, Tobias Friedrich, 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.

Externe Organisation(en)

University of Adelaide
Albert-Ludwigs-Universität Freiburg
Universität Potsdam

Typ

Aufsatz in Konferenzband

Seiten

1704-1711

Anzahl der Seiten

8

Publikationsdatum

07.07.2017

Publikationsstatus

Veröffentlicht

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Artificial intelligence, Computernetzwerke und -kommunikation, Angewandte Informatik, Signalverarbeitung

Elektronische Version(en)

https://doi.org/10.1109/cec.2017.7969507 (Zugang: Geschlossen)