Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization
Lists
Only you see this
Abstract
We investigate how well-performing local search algorithms for small or medium size instances can be scaled up to perform well for large inputs. We introduce a parallel kernelization technique that is motivated by the assumption that graphs in medium to large scale are composed of components which are on their own easy for state-of-the-art solvers but when hidden in large graphs are hard to solve. To show the effectiveness of our kernelization technique, we consider the well-known minimum vertex cover problem and two state-of-the-art solvers called NuMVC and FastVC. Our kernelization approach reduces an existing large problem instance significantly and produces better quality results on a wide range of benchmark instances and real world graphs.
BibTeX
@inproceedings{gao2017scaling,
author = {Wanru Gao and Tobias Friedrich and Timo Kötzing and Frank Neumann},
title = {{Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization}},
booktitle = {Australasian Conference on Artificial Intelligence},
year = {2017},
doi = {10.1007/978-3-319-63004-5\_11},
}Loading related content...