A multi-start iterated greedy algorithm for the minimum weight vertex cover P₃ problem

DOI10.1016/J.AMC.2018.12.067zbMATH Open1428.05299OpenAlexW2910056170MaRDI QIDQ2008933FDOQ2008933

Authors: Lidong Wu, Wenjie Zhang, Jianhua Tu 

Publication date: 26 November 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2018.12.067

Recommendations

• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Approximation algorithms for minimum weight connected 3-path vertex cover
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• On the weighted \(k\)-path vertex cover problem

zbMATH Keywords

combinatorial optimization problemsheuristic algorithmsiterated greedy algorithmminimum weight vertex cover \(P_3\) problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph theory
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• An ant colony optimization algorithm for the minimum weight vertex cover problem
• On the vertex cover \(P_3\) problem parameterized by treewidth
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Multi-Start Methods
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• A faster FPT algorithm for 3-path vertex cover
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems

Cited In (3)

• A new solver for the minimum weighted vertex cover problem
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• Minimum-weight vertex cover problem for two-class resource connection graphs

This page was built for publication: A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2008933)