Greedy Local Search and Vertex Cover in Sparse Random Graphs

DOI10.1007/978-3-642-02017-9_43MaRDI QIDQ3630226zbMATH OpenOpenAlexWikidataFDO

Authors Carsten Witt

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_43

Mathematics Subject Classification ID

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

Recommendations

• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Analysis of greedy algorithm for vertex covering of random graph by cubes
• Vertex Cover Approximations on Random Graphs
• scientific article; zbMATH DE number 1875441
• scientific article; zbMATH DE number 1139976

Cited in

(7)

• Typical performance of approximation algorithms for NP-hard problems
• Analysis of greedy algorithm for vertex covering of random graph by cubes
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Approximating vertex cover using edge-based representations
• Parameterized and Exact Computation
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Limits of local algorithms over sparse random graphs

This page was built for publication: Greedy Local Search and 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 Q3630226)