Analysis of an iterated local search algorithm for vertex cover in sparse random graphs

DOI10.1016/j.tcs.2011.01.010zbMath1237.68197OpenAlexW2052468331WikidataQ57200608 ScholiaQ57200608MaRDI QIDQ418035

Carsten Witt

Publication date: 14 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.01.010

zbMATH Keywords

random graphsvertex coveriterated local searche-phenonemonKarp-Sipser algorithmrandomized search heuristics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (4)

A probabilistic algorithm for vertex cover ⋮ Generalized K-Core Percolation in Networks with Community Structure ⋮ Memetic algorithms outperform evolutionary algorithms in multimodal optimisation ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hybridizing evolutionary algorithms with variable-depth search to overcome local optima
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Runtime analysis of a simple ant colony optimization algorithm
• On the analysis of the \((1+1)\) evolutionary algorithm
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Greedy Local Search and Vertex Cover in Sparse Random Graphs
• Finding a Maximum Independent Set
• Paths in graphs
• STACS 2005
• Automata, Languages and Programming
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

This page was built for publication: Analysis of an iterated local search algorithm for vertex cover in sparse random graphs