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.
Calamoneri, Tiziana; Finocchi, Irene; Manoussakis, Y.; Petreschi, Rossella. (1999). A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs. In Proc. 5th Asian Computing Science Conference (ASIAN'99) (pp. 27- 36). Isbn: 9783540668565. Doi: 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
