Hard graphs for randomized subgraph exclusion algorithms

DOI10.1007/3-540-58218-5_26zbMath1502.68244OpenAlexW1921782964MaRDI QIDQ5054768

Marcus Peinado

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_26

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• Intersection theorems with geometric consequences
• Approximating maximum independent sets by excluding subgraphs
• The greedy coloring is a bad probabilistic algorithm
• Large Cliques Elude the Metropolis Process
• Approximating maximum independent sets by excluding subgraphs

This page was built for publication: Hard graphs for randomized subgraph exclusion algorithms