An efficient heuristic algorithm for solving connected vertex cover problem (Q1720833): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete / rank
 
Normal rank
Property / cites work
 
Property / cites work: PTAS for connected vertex cover in unit disk graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Vertex and edge covers with clustering properties: Complexity and algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover / rank
 
Normal rank
Property / cites work
 
Property / cites work: Depth-first search and the vertex cover problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: A 2-approximation NC algorithm for connected vertex cover and tree cover / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Connected Vertex Covers in Dense Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity and algorithms for the connected vertex cover problem in 4-regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimization by GRASP / rank
 
Normal rank
Property / cites work
 
Property / cites work: A novel local search algorithm with configuration checking and scoring mechanism for the set <i>k</i>‐covering problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Local search with edge weighting and configuration checking heuristics for minimum vertex cover / rank
 
Normal rank
Property / cites work
 
Property / cites work: CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability / rank
 
Normal rank
Property / cites work
 
Property / cites work: NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover / rank
 
Normal rank

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
    0 references
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references