Finding large cliques in sparse semi-random graphs by simple randomized search heuristics

DOI10.1016/j.tcs.2007.06.008zbMath1137.05070OpenAlexW2093042554MaRDI QIDQ2455599

Tobias Storch

Publication date: 25 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2003/26119

zbMATH Keywords

evolutionary algorithmspopulation sizeruntime analysisMaximum clique problemrandomized local search algorithmssemi-random graphs

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items (2)

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Heuristics for semirandom graph problems
• On the analysis of the \((1+1)\) evolutionary algorithm
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Large Cliques Elude the Metropolis Process
• Approximating Maximum Clique by Removing Subgraphs
• Coloring Random and Semi-Random k-Colorable Graphs
• Finding and certifying a large hidden clique in a semirandom graph
• Reducibility among Combinatorial Problems

This page was built for publication: Finding large cliques in sparse semi-random graphs by simple randomized search heuristics