An Efficient Heuristic Algorithm for Solving Connected Vertex Cover Problem

Yongfei Zhang, Jun Wu, Liming Zhang, Peng Zhao, Junping Zhou and Minghao Yin

Mathematical Problems in Engineering, 2018, vol. 2018, 1-10

Abstract:

The connected vertex cover ( ) 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 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.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2018/3935804.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2018/3935804.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:3935804

DOI: 10.1155/2018/3935804

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().