Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold

DOI10.1007/11841036_40zbMath1131.05315OpenAlexW2105105087MaRDI QIDQ5449548

Elias C. Stavropoulos, Alexis C. Kaporis, Lefteris M. Kirousis

Publication date: 11 March 2008

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

Full work available at URL: https://doi.org/10.1007/11841036_40

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (1)

Approximability Distance in the Space of H-Colourability Problems

This page was built for publication: Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold