Approximating vertex cover using edge-based representations

DOI10.1145/2460239.2460248zbMath1369.68312OpenAlexW2011113110MaRDI QIDQ5276116

Thomas Jansen, Christine Zarges, Pietro S. Oliveto

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

representationvertex coverruntime analysisrandom local search\((1+1)\) EA

Mathematics Subject Classification ID

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

Related Items (7)

Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem ⋮ Runtime analysis of RLS and \((1 + 1)\) EA for the dynamic weighted vertex cover problem ⋮ Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree 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

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