Bounds on the max and min bisection of random cubic and random 4-regular graphs
From MaRDI portal
Publication:1885048
DOI10.1016/S0304-3975(03)00236-6zbMath1070.68119MaRDI QIDQ1885048
Nicholas C. Wormald, Maria J. Serna, Josep Diaz, Norman Do
Publication date: 27 October 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Maximum cliques in graphs with small intersection number and random intersection graphs, Bounds on the bisection width for random \(d\)-regular graphs, Properties of regular graphs with large girth via local algorithms, On the minimum bisection of random 3-regular graphs, Factors of IID on Trees, The cook-book approach to the differential equation method, Balanced polychromatic 2-coloring of triangulations, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Cites Work
- The isoperimetric number of random regular graphs
- Analysis of greedy algorithms on graphs with bounded degrees
- A note on approximating Max-Bisection on regular graphs
- A Polylogarithmic Approximation of the Minimum Bisection
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item