Fixed-parameter evolutionary algorithms and the vertex cover problem

DOI10.1007/S00453-012-9660-4MaRDI QIDQ1949737zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, F. Neumann

Publication date 16 May 2013

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

randomized algorithmsevolutionary algorithmsfixed-parameter tractabilityvertex cover

Mathematics Subject Classification ID

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

Recommendations

• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• An improved fixed-parameter algorithm for vertex cover
• On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms
• Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem
• Approximating vertex cover using edge-based representations

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1962832 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 5485575 (Why is no real title available?)
• scientific article; zbMATH DE number 3361920 (Why is no real title available?)
• Ant colony optimization.
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• Crossover can provably be useful in evolutionary computation
• Evolvability
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Improved Parameterized Upper Bounds for Vertex Cover
• Introduction to algorithms
• Introduction to evolutionary computing
• Multiway cuts in node weighted graphs
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• STACS 2005
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Vertex cover: Further observations and further improvements
• Vertex packings: Structural properties and algorithms

Cited in

(15)

• Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints
• scientific article; zbMATH DE number 1946631 (Why is no real title available?)
• Runtime performance of evolutionary algorithms for the chance-constrained makespan scheduling problem
• Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem
• Fixed parameter multi-objective evolutionary algorithms for the W-separator problem
• Bidirectional evolutionary heuristic for the minimum vertex-cover problem
• On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• A simulated evolution-based solution of the cover 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
• Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
• Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

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

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