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

DOI10.1016/J.AMC.2018.12.067MaRDI QIDQ2008933zbMATH OpenOpenAlexFDO

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

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)

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₃ problem
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• On the weighted \(k\)-path vertex cover problem

Cites work

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

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)