Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
type: Item
instance of: scholarly article
title: Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
zbMATH Open document ID: 1237.68197
author: Carsten Witt
published in: Theoretical Computer Science
publication date: 2012-05-14T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 6034872
zbMATH Keywords: randomized search heuristics
zbMATH Keywords: iterated local search
zbMATH Keywords: vertex cover
zbMATH Keywords: random graphs
zbMATH Keywords: Karp-Sipser algorithm
zbMATH Keywords: e-phenonemon
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.01.010
OpenAlex ID: W2052468331
Wikidata QID: Q57200608
cites work: Q4385084
cites work: Paths in graphs
cites work: Introduction to algorithms
cites work: On the analysis of the \((1+1)\) evolutionary algorithm
cites work: Q5538132
cites work: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
cites work: Q4418669
cites work: Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
cites work: Q5472387
cites work: Q4142699
cites work: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
cites work: Runtime analysis of a simple ant colony optimization algorithm
cites work: Hybridizing evolutionary algorithms with variable-depth search to overcome local optima
cites work: Finding a Maximum Independent Set
cites work: Automata, Languages and Programming
cites work: STACS 2005
cites work: Greedy Local Search and Vertex Cover in Sparse Random Graphs
DOI: 10.1016/J.TCS.2011.01.010
description: scientific article; zbMATH DE number 6034872