NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

DOI10.1613/JAIR.3907zbMath1280.90098arXiv1402.0584OpenAlexW2122448854MaRDI QIDQ4917618

Kaile Su, Shaowei Cai, Chuan Luo, Abdul Sattar

Publication date: 2 May 2013

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

Full work available at URL: https://arxiv.org/abs/1402.0584

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ A vertex weighting-based double-tabu search algorithm for the classical \(p\)-center problem ⋮ Dual-neighborhood iterated local search for routing and wavelength assignment ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ An efficient local search algorithm for minimum positive influence dominating set problem ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ Towards faster local search for minimum weight vertex cover on massive graphs ⋮ Can local optimality be used for efficient data reduction? ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems ⋮ Local search for Boolean satisfiability with configuration checking and subscore ⋮ CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ NuMVC ⋮ Backdoors to tractable answer set programming

Uses Software

• BHOSLIB
• DIMACS

This page was built for publication: NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover