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

DOI10.1016/J.TCS.2011.01.010zbMATH Open1237.68197OpenAlexW2052468331WikidataQ57200608 ScholiaQ57200608MaRDI QIDQ418035FDOQ418035

Authors: 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

Recommendations

• Greedy Local Search and Vertex Cover in Sparse Random Graphs
• Approximating vertex cover using edge-based representations
• Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• A probabilistic algorithm for vertex cover
• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• Approximating vertex cover using edge-based representations
• A greedy probabilistic heuristic for graph black-and-white anticoloring
• Generalized \(K\)-core percolation in networks with community structure
• A \((2-\varepsilon)\)-approximation ratio for vertex cover problem on special graphs
• Greedy Local Search and Vertex Cover in Sparse Random Graphs

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

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