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 SizeFormat 
RA_hdl_109190.pdf
  Restricted Access
Restricted Access330.03 kBAdobe PDFView/Open
hdl_109190.pdfAccepted version521.22 kBAdobe PDFView/Open


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