Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
From MaRDI portal
Publication:3145840
DOI10.1002/rsa.20471zbMath1255.05102DBLPjournals/rsa/KardosKV12arXiv1108.6280OpenAlexW3125518523WikidataQ57601386 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 (5)
Properties of regular graphs with large girth via local algorithms ⋮ Factors of IID on Trees ⋮ Local approximation of the maximum cut in regular graphs ⋮ Hypergraph cuts above the average ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs
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
This page was built for publication: Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
