Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

DOI10.1002/rsa.20471zbMath1255.05102arXiv1108.6280WikidataQ57601386 ScholiaQ57601386MaRDI QIDQ3145840

František Kardoš, Jan Volec, Daniel Král'

Publication date: 14 December 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.6280

zbMATH Keywords

random graphs; cubic graphs; large girth; edge-cut

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C80: Random graphs (graph-theoretic aspects)

Related Items

Factors of IID on Trees, Local approximation of the maximum cut in regular graphs, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Properties of regular graphs with large girth via local algorithms, Hypergraph cuts above the average

Uses Software

• MPFR
• mctoolbox
• Mulprec

Cites Work

• Unnamed Item
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Differential equations for random processes and random graphs
• Bounds on the bisection width for random \(d\)-regular graphs
• Large independent sets in regular graphs of large girth
• Numerical Methods in Scientific Computing, Volume I
• Induced Forests in Regular Graphs with Large Girth
• MPFR
• On the bipartite density of regular graphs with large girth
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Accuracy and Stability of Numerical Algorithms
• On the Independent Domination Number of Random Regular Graphs
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimization via enumeration: A new algorithm for the max cut problem