An efficient heuristic algorithm for solving connected vertex cover problem
type: Item
instance of: scholarly article
title: An efficient heuristic algorithm for solving connected vertex cover problem
zbMATH Open document ID: 1427.90305
DOI: 10.1155/2018/3935804
author: Yongfei Zhang
author: Jun Wu
author: Peng Zhao
author: Junping Zhou
author: Minghao Yin
author: Liming Zhang
published in: Mathematical Problems in Engineering
publication date: 2019-02-08T00:00:00Z
review text: Summary: The connected vertex cover \((C V C)\) problem, which has many important applications, is a variant of the vertex cover problem, such as wireless network design, routing, and wavelength assignment problem. A good algorithm for the problem can help us improve engineering efficiency, cost savings, and resources consumption in industrial applications. In this work, we present an efficient algorithm GRASP-CVC (Greedy Randomized Adaptive Search Procedure for Connected Vertex Cover) for \(C V C\) in general graphs. The algorithm has two main phases, i.e., construction phase and local search phase. In the construction phase, to construct a high quality feasible initial solution, we design a greedy function and a restricted candidate list. In the local search phase, the configuration checking strategy is adopted to decrease the cycling problem. The experimental results demonstrate that GRASP-CVC is better than other comparison algorithms in terms of effectivity and efficiency.
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7018890
describes a project that uses: CCLS
describes a project that uses: NuMVC
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2018/3935804
OpenAlex ID: W2889606199
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: PTAS for connected vertex cover in unit disk graphs
cites work: Vertex and edge covers with clustering properties: Complexity and algorithms
cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
cites work: Depth-first search and the vertex cover problem
cites work: A 2-approximation NC algorithm for connected vertex cover and tree cover
cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
cites work: Connected Vertex Covers in Dense Graphs
cites work: Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
cites work: Optimization by GRASP
cites work: A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem
cites work: Local search with edge weighting and configuration checking heuristics for minimum vertex cover
cites work: CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
cites work: NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
description: scientific article; zbMATH DE number 7018890