Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3

DOI10.1016/j.jda.2007.02.002zbMath1167.68060OpenAlexW2113647243MaRDI QIDQ1018104

Zsolt Tuza, Cristina Bazgan

Publication date: 13 May 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.02.002

zbMATH Keywords

approximation algorithmmaximum cutcubic graphvertex decompositionunicyclic graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Online maximum directed cut

Cites Work

• Unnamed Item
• Unnamed Item
• Application of cut polyhedra. I
• MAX CUT in cubic graphs
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Linear-Time Approximation Algorithms for the Max Cut Problem
• ON DISJOINT CYCLES
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Node-and edge-deletion NP-complete problems

This page was built for publication: Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3