Approximating vertex cover using edge-based representations

DOI10.1145/2460239.2460248MaRDI QIDQ5276116zbMATH OpenOpenAlexFDO

Authors Thomas Jansen, Pietro S. Oliveto, Christine Zarges

Publication date 14 July 2017

Published in Proceedings of the twelfth workshop on Foundations of genetic algorithms XII (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2460239.2460248

zbMATH Keywords

vertex coverrepresentationruntime analysisrandom local search\((1+1)\) EA

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem
• Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Greedy Local Search and Vertex Cover in Sparse Random Graphs
• On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms

Cited in

(12)

• Fixed-parameter evolutionary algorithms and the vertex cover problem
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Runtime performance of evolutionary algorithms for the chance-constrained makespan scheduling problem
• The runtime of the compact genetic algorithm on jump functions
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Approximation Algorithms for Edge-Covering Problem
• Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem
• Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
• Approximating V<scp>ertex</scp> C<scp>over</scp> using Structural Rounding
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

This page was built for publication: Approximating vertex cover using edge-based representations

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