We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel algorithm, running on a CRCW PRAM 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.
A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs / Calamoneri, Tiziana; Finocchi, Irene; Manoussakis, Y.; Petreschi, Rossella. - Proc. 5th Asian Computing Science Conference (ASIAN'99), (1999), pp. 27-36. (Asian Computing Science Conference, Pucket, Tailandia, December 10–12,1999). [10.1007/3-540-46674-6_4].
A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs
Irene Finocchi;
1999
Abstract
We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel algorithm, running on a CRCW PRAM 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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
