Loading...
Please wait, while we are loading the content...
Similar Documents
A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs (1999)
| Content Provider | CiteSeerX |
|---|---|
| Author | Calamoneri, T. Finocchi, I. Manoussakis, Y. Petreschi, R. |
| Description | 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 Format | |
| Language | English |
| Publisher Date | 1999-01-01 |
| Publisher Institution | Advances in Computing Science - ASIAN'99, Lect. Notes in Comp. Science 1742, Springer Verlag Ed |
| Access Restriction | Open |
| Subject Keyword | Approximation Ratio Cubic Graph Max Cut Problem Time Parallel Algorithm Crcw Pram Special Case Maximum Cut Problem Parallel Approximation Algorithm Known Parallel Approximation Ratio |
| Content Type | Text |
| Resource Type | Article |
