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

Cristina Bazgan Zsolt Tuza

Published in: J. Discrete Algorithms (2008)

Keyphrases

max cut
graph model
planar graphs
np complete problems
np hard
graph partitioning
spectral graph
np complete
special case
approximation algorithms
closed form
data clustering
branch and bound algorithm
graph coloring