On max cut in cubic graphs

DOI10.1080/10637190127724MaRDI QIDQ4409003zbMATH OpenOpenAlexFDO

Authors Irene Finocchi, Rossella Petreschi, Tiziana Calamoneri, Y. Manoussakis

Publication date 29 June 2003

Full work available at URL https://doi.org/10.1080/10637190127724

zbMATH Keywords

bipartite graphscubic graphsmaximum cut problem

Mathematics Subject Classification ID

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

Recommendations

• A parallel approximation algorithm for the max cut problem on cubic graphs
• MAX CUT in cubic graphs
• Efficient maximal cubic graph cuts
• scientific article; zbMATH DE number 1787231
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3

Cited in

(8)

• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Max-cut in circulant graphs
• A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• MAX CUT in cubic graphs
• Efficient maximal cubic graph cuts
• A parallel approximation algorithm for the max cut problem on cubic graphs
• Use of MAX-CUT for Ramsey Arrowing of Triangles

This page was built for publication: On max cut in cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4409003)