An efficient local search framework for the minimum weighted vertex cover problem

DOI10.1016/j.ins.2016.08.053zbMath1428.90183OpenAlexW2509952555MaRDI QIDQ2282264

Shuli Hu, Minghao Yin, Ruizhi Li, Haochen Zhang

Publication date: 7 January 2020

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2016.08.053

zbMATH Keywords

local searchminimum weighted vertex covermassive graph instancesscoring strategyweighted configuration checking

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (6)

Solving the set packing problem via a maximum weighted independent set heuristic ⋮ MLQCC: an improved local search algorithm for the set k‐covering problem ⋮ Towards faster local search for minimum weight vertex cover on massive graphs ⋮ Large scale continuous global optimization based on micro differential evolution with local directional search ⋮ Local search for diversified top-\(k\) clique search problem ⋮ New heuristic approaches for maximum balanced biclique problem

Uses Software

• NuMVC
• CCASat

Cites Work

• Unnamed Item
• On the weighted \(k\)-path vertex cover problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Local search for Boolean satisfiability with configuration checking and subscore
• Optimal topological design for distributed estimation over sensor networks
• Exact solutions to generalized vertex covering problems: a comparison of two models
• Measuring the impact of MVC attack in large complex networks
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• An ant colony optimization algorithm for the minimum weight vertex cover problem
• On the hardness of approximating minimum vertex cover
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• Hybrid evolutionary search for the minimum sum coloring problem of graphs
• Incremental learning for \(\nu\)-support vector regression
• Dense community detection in multi-valued attributed networks
• The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
• A novel evolutionary formulation of the maximum independent set problem
• Extending the MAX algorithm for maximum independent set
• Advice complexity of maximum independent set in sparse and bipartite graphs
• The maximum independent set problem in subclasses of subcubic graphs
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
• Combining Edge Weight and Vertex Weight for Minimum Vertex Cover Problem
• On independent sets in random graphs
• A Greedy Heuristic for the Set-Covering Problem
• Tabu Search—Part I
• Tabu Search—Part II
• Optimized Crossover for the Independent Set Problem
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

This page was built for publication: An efficient local search framework for the minimum weighted vertex cover problem