An efficient heuristic algorithm for solving connected vertex cover problem

DOI10.1155/2018/3935804zbMath1427.90305OpenAlexW2889606199MaRDI QIDQ1720833

Junping Zhou, Jun Wu, Minghao Yin, Peng Zhao, Yongfei Zhang, Li-Ming Zhang

Publication date: 8 February 2019

Published in: Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2018/3935804

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• NuMVC
• CCLS

Cites Work

• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Vertex and edge covers with clustering properties: Complexity and algorithms
• PTAS for connected vertex cover in unit disk graphs
• Depth-first search and the vertex cover problem
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Optimization by GRASP
• Connected Vertex Covers in Dense Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

This page was built for publication: An efficient heuristic algorithm for solving connected vertex cover problem