The MAX-CUT of sparse random graphs

MaRDI QIDQ5743397zbMATH OpenFDO

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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(9)

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

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)