Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
From MaRDI portal
Publication:3145840
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
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
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