Algoritma Paralel Pewarnaan Graph (Graph Coloring)

Persoalan pewarnaan Graph (Graph Coloring) adalah mencari banyaknya warna yang dapat digunakan untuk mewarnai setiap vertex yang ada pada sebuah Graph sehingga tidak ada vertex yang bertetangga memiliki warna yang sama.

Asumsikan bahwa kita memiliki sebuah Graph dengan n buah vertex. Kemudian kita membuat sebuah matriks tetangga (matrik adjacency) n x n dan sebuah bilangan konstan c , sebuah prosessor disiapkan untuk setiap kemungkinan pewarnaan Graph. Contoh,  prosesor \(P(i_0,i_1, … , i_{n-1})\) berkaitan dengan  pewarnaan vertex 0 dengan warna \(i_0\), pewarnaan vertex 1 dengan warna \(i_1\), …  pewarnaan vertex n-1  dengan warna \(i_{n-1}\)

Setiap prosesor pada awalnya mengatur nilainya dalam candidate array berdimensi-n ke nilai 1 (satu). Kemudian menghabiskan waktu \(\Theta (n^{2})\) untuk menentukan apakah untuk pewarnaan pada vertex tertentu dapat dilakukan, dua vertex yang bertetangga telah diberi warna yang sama. Jika A[j,k] = 1 dan \(i_j = i_k\), maka proses pewarnaan salah, karena A[j,k] = 1 berarti vertex j dan k bertetangga, dan \(i_j = i_k\) artinya j dan k memiliki warna yang sama. Jika prosesor mendeteksi pewarnaan yang salah ini, dia akan mengubah nilainya di candidate array menjadi 0. Setelah \(n^2\) kali pembandingan, jika ada elemen di candidate array yang masih bernilai 1, maka pewarnaan dinyatakan benar. Dengan menjumlahkan semua elemen \(c^n\) dalam candidate array, maka kita dapat menyatakan apakah proses pewarnaan dapat dilakukan (lihat gambar dan algoritma di bawah ini)

Kompleksitas : \(\Theta (n^2)\) dengan menggunakan n buah Prosesor.