A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs
We deal with the maximum cut problem in parallel for cubic
graphs. Namely, we present new theoretical results characterizing the
cardinality of the cut. These results make it possible to design a
simple O(log n) time parallel algorithm, running on a CRCW P-RAM
with O(n) processors. The approximation ratio of our algorithm is
1.3 and improves the best known parallel approximation ratio,
i.e. 2, in the special case of cubic graphs. Moreover, we are able
to guarantee that the size of the found cut is at least
{9g-3}/{8g}n, where g is the odd girth of the input graph.
The results of a wide experimentation round off the paper.
conference
version
journal
version