Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess

DOI10.1613/JAIR.5443zbMATH Open1418.68164OpenAlexW2739688939MaRDI QIDQ5370992FDOQ5370992

Authors Shaowei Cai, Chuan Luo, Jinkun Lin

Publication date 24 October 2017

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.5443

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Towards faster local search for minimum weight vertex cover on massive graphs
• A warning propagation-based linear-time-and-space algorithm for the minimum vertex cover problem on giant graphs
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities
• NuMVC: an efficient local search algorithm for minimum vertex cover
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover

Cited in

(9)

• On solving simplified diversified top-\(k\,s\)-plex problem
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities
• SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• A warning propagation-based linear-time-and-space algorithm for the minimum vertex cover problem on giant graphs
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Towards faster local search for minimum weight vertex cover on massive graphs
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
• An improved configuration checking-based algorithm for the unicost set covering problem

This page was built for publication: Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370992)