An efficient heuristic algorithm for solving connected vertex cover problem (Q1720833): Difference between revisions
From MaRDI portal
Latest revision as of 03:07, 18 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient heuristic algorithm for solving connected vertex cover problem |
scientific article |
Statements
An efficient heuristic algorithm for solving connected vertex cover problem (English)
0 references
8 February 2019
0 references
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.
0 references
0 references
0 references