Fixed-parameter evolutionary algorithms and the vertex cover problem

DOI10.1007/s00453-012-9660-4zbMath1262.68180OpenAlexW2088415500MaRDI QIDQ1949737

Frank Neumann, Stefan Kratsch

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9660-4

zbMATH Keywords

evolutionary algorithmsrandomized algorithmsvertex coverfixed-parameter tractability

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (9)

Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem ⋮ Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem ⋮ Runtime analysis of RLS and \((1 + 1)\) EA for the dynamic weighted vertex cover problem ⋮ Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints ⋮ 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 ⋮ Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Crossover can provably be useful in evolutionary computation
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Vertex Cover: Further Observations and Further Improvements
• Vertex packings: Structural properties and algorithms
• Multiway cuts in node weighted graphs
• STACS 2005
• Improved Parameterized Upper Bounds for Vertex Cover
• Evolvability
• Introduction to evolutionary computing

This page was built for publication: Fixed-parameter evolutionary algorithms and the vertex cover problem