Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109190
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Fixed-parameter single objective search heuristics for minimum vertex cover |
Author: | Gao, W. Friedrich, T. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2016 / Handl, J., Hart, E., Lewis, P., Lopez-Ibanez, M., Ochoa, G., Paechter, B. (ed./s), vol.9921 LNCS, pp.740-750 |
Publisher: | Springer |
Issue Date: | 2016 |
Series/Report no.: | Lecture Notes in Computer Science (LNCS, vol. 9921) |
ISBN: | 9783319458229 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | 14th International Conference on Parallel Problem Solving from Nature (PPSN XIV) (17 Sep 2016 - 21 Sep 2016 : Edinburgh, UK) |
Editor: | Handl, J. Hart, E. Lewis, P. Lopez-Ibanez, M. Ochoa, G. Paechter, B. |
Statement of Responsibility: | Wanru Gao, Tobias Friedrich, and Frank Neumann |
Abstract: | We consider how well-known branching approaches for the classical minimum vertex cover problem can be turned into randomized initialization strategies with provable performance guarantees and investigate them by experimental investigations. Furthermore, we show how these techniques can be built into local search components and analyze a basic local search variant that is similar to a state-of-the-art approach called NuMVC. Our experimental results for the two local search approaches show that making use of more complex branching strategies in the local search component can lead to better results on various benchmark graphs. |
Rights: | © Springer International Publishing AG 2016 |
DOI: | 10.1007/978-3-319-45823-6_69 |
Grant ID: | http://purl.org/au-research/grants/arc/DP140103400 |
Published version: | http://dx.doi.org/10.1007/978-3-319-45823-6_69 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_109190.pdf Restricted Access | Restricted Access | 330.03 kB | Adobe PDF | View/Open |
hdl_109190.pdf | Accepted version | 521.22 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.