The MAX-CUT of sparse random graphs

zbMATH Open1423.05150MaRDI QIDQ5743397FDOQ5743397

Authors: Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, Vlady Ravelomanana 

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095140

Recommendations

• On the max-cut of sparse random graphs
• Extremal cuts of sparse random graphs
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• On the maximal cut in a random hypergraph
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Density (toughness, etc.) (05C42)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Title not available (Why is that?)
• The number of connected sparsely edged graphs
• The birth of the giant component
• Title not available (Why is that?)
• Some optimal inapproximability results
• Title not available (Why is that?)
• The first cycles in an evolving graph
• Title not available (Why is that?)
• The 3-XORSAT threshold.
• Counting connected graphs inside-out
• On the Number of Husimi Trees
• Random MAX SAT, random MAX CUT, and their phase transitions
• Satisfiability threshold for random XOR-CNF formulas
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The number of connected sparsely edged graphs. III. Asymptotic results
• How frequently is a system of 2-linear Boolean equations solvable?
• MAX k‐CUT and approximating the chromatic number of random graphs
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• Limit Theorems for Random MAX-2-XORSAT
• Random 2-XORSAT at the Satisfiability Threshold

Cited In (9)

• On extremal subgraphs of random graphs
• Maximal induces trees in sparse random graphs
• A probabilistic result for the max-cut problem on random graphs
• Convergence of maximum bisection ratio of sparse random graphs
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• On the max-cut of sparse random graphs
• On the maximal cut in a random hypergraph
• Extremal cuts of sparse random graphs
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

This page was built for publication: The MAX-CUT of sparse random graphs

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