Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
From MaRDI portal
Publication:3373669
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
Cited in
(12)- On the largest component of the critical random digraph
- Automata, Languages and Programming
- Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
- The critical random graph, with martingales
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- The MAX-CUT of sparse random graphs
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- The continuum limit of critical random graphs
- Swendsen-Wang algorithm on the mean-field Potts model
- The critical window in random digraphs
- Critical random graphs and the structure of a minimum spanning tree
- The number of satisfying assignments of random 2‐SAT formulas
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)
