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

DOI10.1017/S096354830500725XzbMATH Open1082.05519MaRDI QIDQ3373669FDOQ3373669

Gregory B. Sorkin, Alex Scott

Publication date: 13 March 2006

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

Recommendations

• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• An exact algorithm for MAX-CUT in sparse graphs
• On the max-cut of sparse random graphs
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Linear time algorithms for finding sparsest cuts in various graph classes
• Automata, Languages and Programming
• The MAX-CUT of sparse random graphs
• MAX-CUT has a randomized approximation scheme in dense graphs
• On the hardness of approximating Multicut and Sparsest-Cut

zbMATH Keywords

random graphalgorithmrandom walksindependent setvertex coverbinomial distributions

Mathematics Subject Classification ID

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

Cited In (11)

• Title not available (Why is that?)
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
• On the largest component of the critical random digraph
• Automata, Languages and Programming
• The critical window in random digraphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• The number of satisfying assignments of random 2‐SAT formulas
• The critical random graph, with martingales
• Swendsen‐Wang algorithm on the mean‐field Potts model
• The continuum limit of critical random graphs
• Critical random graphs and the structure of a minimum spanning tree

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3373669)