Bounds on the max and min bisection of random cubic and random 4-regular graphs

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)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

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