Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time

DOI10.1017/S096354830500725XzbMath1082.05519MaRDI QIDQ3373669

Gregory B. Sorkin, Alexander D. Scott

Publication date: 13 March 2006

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

algorithmrandom walksindependent setrandom graphvertex coverbinomial distributions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items (9)

The critical window in random digraphs ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ The continuum limit of critical random graphs ⋮ Swendsen‐Wang algorithm on the mean‐field Potts model ⋮ The critical random graph, with martingales ⋮ Critical random graphs and the structure of a minimum spanning tree ⋮ Unnamed Item

Uses Software

• MAX-2-SAT

This page was built for publication: Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time