Tugas Algoritma & Pengolahan Pararel

Kelompok:

Andhika Nugrahatama 50405070
Mariska Chairunnisa 50405457
M Arief Rahman Hakim 50405485
Santoso Budiman 50405665
Yang Citra Derisa 50405757

Kelas 4IA08

New Graph Coloring Algorithms

Hussein Al-Omari, Khair Eddin Sabri

Abstraksi:
Dua algoritma pewarnaan graf heuristik yang didasarkan dari algoritma heuristik yang telah dikenal, telah diperkenalkan. Salah satu diantaranya adalah merupakan modifikasi dari Algoritma Pengurutan Derajat Tertinggi, dan satu yang lain merupakan hasil modifikasi algoritma Pengurutan Derajat Saturasi. Kedua algoritma baru yang diperkenalkan di paper ini diperbandingkan secara empiris dalam hal warna yang digunakan dengan beberapa algoritma pewarnaan graf yang terkenal, seperti Pengurutan derajat tertinggi (LDO), First Fit (FF), Pengurutan derajat tersaturasi (SDO), dan Pengurutan Derajat insidens (IDO). Sebagai hasil dari perbandingan ini, ditemukan bahwa algoritma yang ditawarkan lebih baik dibandingkan dengan algoritma sebelumnya dalam hal warna yang digunakan.

Kata kunci: Algoritma pewarnaan graf, derajat urutan, algoritma first-fit.

INTRODUCTION

Pewarnaan graf didefinisikan sebagai mewarnai simpul dari graf dengan jumlah warna sesedikit mungkin tanpa ada dua simpul bersebelahan memiliki warna yang sama. Contohnya, linked list memerlukan dua warna, begitu juga dengan binary search tree. Pewarnaan graf memiliki penggunaan yang luas, misalnya: Perkiraan sparse Jacobian, Penjadwalan dan pendaftaran alokasi.

Pewarnaan graf G = (V, E) merupakan pemetaan c:v->s , dimana “s” merupakan set warna hingga, sedemikian hingga jika vw anggota E maka c(v) tidak sama dengan c(w). Dengan kata lain, simpul yang bersebelahan tidak diberikan warna yang sama [1]. Masalah yang timbul adalah pewarnaan graf tanpa ada simpul bersebelahan yang memiliki warna yang sama. Angka kromatik X(G) merupakan jumlah warna minimal yang diperlukan untuk mewarnai graf G. Graf G merupakan k_kromatik jika X(G) = k dan Graf G merupakan k_colorable jika X(G) < = k.

Pewarnaan graf merupakan salah satu model yang paling berguna dalam teori graf. Pewarnaan graf digunakan untuk memecahkan permasalahan penjadwalan sekolah, alokasi register komputer, alokasi bandwidth elektronik, dan banyak aplikasi lain [2]

Dalam tulisan ini, dua algoritma pewarnaan graf heurustik baru, yang berdasarkan algoritma heuristik yang telah dikenal, telah diperkenalkan. Salah satunya adalah modifikasi dari algoritma Pengurutan derajat tertinggi (LDO), dan lainnya merupakan salah satu modifikasi dari algoritma Pengurutan derajat tersaturasi (SDO). Kedua algoritma usulan baru dalam karya ini, yang dibandingkan secara empiris dalam hal warna yang digunakan dengan beberapa algoritma pewarnaan graf heuristik yang telah dikenal seperti: Pengurutan derajat tertinggi (LDO), First Fit (FF), Pengurutan derajat tersaturasi (SDO), dan Pengurutan Derajat insidens (IDO). Sebagai hasil dari perbandingan ini, ditemukan bahwa algoritma yang diusulkan lebih baik daripada algoritma asli dalam hal jumlah warna yang digunakan.

Di sini, kita menginvestigasi beberapa algoritma pewarnaan graf heuristik (FF, FDO, SDO, dan LDO), dan kemudian dengan memodifikasi beberapa dari mereka, kami memperkenalkan dua algoritma baru yang telah dimodifikasi.

Algoritma pewarnaan graf: Ada banyak teknik sekuensial heuristik untuk mewarnai graf. Salah satunya adalah Pewarnaan graf Greedy. Teknik ini berfokus pada pemilihan simpul berikutnya yang akan diwarnai dengan hati-hati. Dalam algoritma heuristik ini, sekali simpul diberi warna, tidak dapat diubah lagi. Di bawah ini, kami akan menjelaskan teknik first fit dan pengurutan berdasarkan warna.

a. First Fit: Algoritma First fit merupakan algoritma yang termudah dan tercepat dalam teknik pewarnaan heuristik greedy. Algoritma memberikan secara berurutan kepada setiap simpul warna terendah yang dapat diberikan. Algoritma ini memiliki keuntungan yaitu sangat sederhana dan cepat dan dapat diimplementasikan untuk berjalan dalam O (n) [2,3].

b. Pengurutan berbasis derajat: algoritma ini menyediakan strategi yang lebih baik dalam mewarnai graf. Menggunakan kriteria pemilihan tertentu untuk memilih simpul yang akan diwarnai. Strategi ini lebih baik dibandingkan dengan First Fit yang memilih simpul secara acak. Beberapa strategi untuk memilih simpul berikutnya yang akan diwarnai telah diusulkan seperti:

Pengurutan derajat tertinggi (LDO): Algoritma ini memilih simpul yang memiliki tetangga paling banyak. Secara intuitif, LDO memberikan pewarnaan yang lebih baik daripada First Fit. Algoritma ini dapat diterapkan untuk berjalan dalam O([n.sup.2]) [2,3].

Pengurutan derajat tersaturasi (SDO): Derajat tersaturasi simpul didefinisikan sebagai jumlah simpul bersebelahan yang memiliki warna berbeda. Secara intuitif, Algoritma heuristik ini memberikan pewarnaan yang lebih baik daripada LDO karena dapat diterapkan untuk berjalan dalam O ([n.sup.3]) [2,3].

Pengurutan Derajat insidens (IDO): Sebuah modifikasi dari algoritma SDO adalah pengurutan derajat insidens, Derajat insidens dari simpul didefinisikan sebagai jumlah simpul berwarna yang berdekatan. Algoritma heuristik ini dapat diterapkan untuk berjalan dalam O ([n.sup.2]) [2,3].

Usulan algoritma: Dalam studi ini, dua algoritma heuristik pewarnaan graf baru telah diperkenalkan berdasarkan algoritma yang telah dikenal. Kedua algoritma usulan baru dijelaskan dalam bagian berikut.

Usulan algoritma 1: Dalam algoritma ini, kami memodifikasi algoritma Pengurutan derajat tertinggi (LDO) dengan menggabungkannya dengan Pengurutan Derajat insidens (IDO)

Algoritma ini bekerja sebagai LDO, tetapi ketika kami menemukan bahwa ada dua node yang memiliki derajat yang sama, Ido digunakan untuk memilih di antara mereka. Ada dua kriteria untuk memilih simpul yang akan diwarnai:
* Jumlah vektor terhubung ke vertex LDO.
* Jumlah berwarna vektor terhubung ke vertex Ido.

Input: set node (grafik) ([n.sub.1], [n.sub.2], [n.sub.3], ... [n.sub.m]) Output: nodes berwarna dan total node jumlah warna.

while (NoOfColoredNodes < m)
{
max=-1
for I = 1 to m
{
if (!colored([n.sub.i]))
{
d = Degree([n.sub.i])
if(d>max)
{
max = d
index = i
}
if(d = max)
if(ID([n.sub.i]) > ID([n.sub.index])
//ID(Incidence Degree)
index = i
}
Color([n.sub.index])
NoOfColoredNodes =
NoOfColoredNodes + 1
}
}

Heuristis ini dapat diterapkan untuk berjalan dalam O ([n.sup.2]) sebagai LDO.

Usulan algoritma 2 : Dalam algoritma ini, kami menggabungkan kedua the Saturated Degree Ordering (SDO), and the Largest Degree Ordering (LDO).

Algoritma yang bekerja sebagai SDO, tetapi apabila terdapat dua node memiliki gelar yang sama, kami menggunakan LDO untuk memilih di antara mereka. Jadi ada dua kriteria untuk memilih node berikutnya untuk diwarnai :

* Jumlah warna sekitar puncak, SDO.

* Jumlah vektor sekitar puncak, LDO.

Input: set node (grafik) ([n.sub.1], [n.sub.2], [n.sub.3 ],….,[ n.sub.m]) Output: node berwarna dan total jumlah warna

while (NoOfColoredNodes < m)
{
Max = -1
for I = 1 to m
{
if (!colored([n.sub.i]))
{
d = SD([n.sub.i])
//SD( Saturated Degree)
if(d > max)
{
max = d
index = i
}
if (d = max)
if(Degree([n.sub.i]) >
Degree([n.sub.index]))
index=i
}
Color([n.sub.index])
NoOfColoredNodes =
NoOfColoredNodes + 1
}
}

Heuristis ini dapat diterapkan untuk berjalan dalam O ([n.sup.3]) sebagai SDO.

HASIL

Kami menerapkan empat heuristis grafik pewarnaan (FF, LDO, Ido, SDO) di samping dua algoritma yang diusulkan.

Kami juga digunakan acak grafik yang berbeda jumlah vektor dan densities. Hasil yang ditampilkan dalam Tabel 1 ditemukan empirically oleh pelaksana dan semua berjalan di atas algorithms.

Tabel 1 menunjukkan temuan sebagai berikut:

* Pertama Fit adalah algoritma yang terburuk algoritma sehubungan dengan jumlah warna yang digunakan.

* LDO menggunakan warna yang lebih kecil daripada jumlah Ido.

* SDO menggunakan warna yang lebih kecil daripada jumlah Ido dan LDO

Algoritma yang diusulkan 1 (modifikasi dari LDO) lebih baik dari LDO dalam jumlah warna yang digunakan.

* Algoritma yang diusulkan 2 (modifikasi dari SDO) lebih baik dari SDO dalam jumlah warna yang digunakan.
* Algoritma yang diusulkan 2 menggunakan sedikitnya jumlah warna untuk mewarnai grafik.

KESIMPULAN

Dalam tulisan ini, kami memperkenalkan dua warna baru heuristis algoritma grafik berdasarkan memodifikasi dan memperbaiki dikenal yg dpt tembus ones. Salah satunya adalah perbaikan pada modifikasi Largest Gelar Diurutkan (LDO) dengan menggabungkan dengan Incident Gelar Diurutkan (Ido), dan satu lainnya merupakan modifikasi dari perbaikan jenuh Gelar Diurutkan (SDO) dengan menggabungkan dengan Largest Gelar Diurutkan ( LDO). Empirically telah menunjukkan bahwa jumlah warna yang digunakan dalam algoritma usulan adalah lebih baik daripada yang asli.

REFERENSI

[1.] Baase, S. and A. Van Gelder, 2000. Computer Algorithms: Introduction to Design and Analysis. Third Edn., Addison Wesley.

[2.] Klotz, W., 2002. Graph coloring algorithms: www.math.tuclausthal.de/Arbeitsgruppen/Diskrete Optimierung/publications/2002/gca.pdf.

[3.] Gebremedhin, A.H., 1999. Parallel Graph Coloring. Thesis University of Bergen Norway Spring.

Dr. Hussein Al-Omari and Khair Eddin Sabri

(1) Computer Science Department, School of Computer Science and Information Technology Applied Science University, Amman, Jordan
Related Results

* Cloud Computing Also Hit by IT-Spending Cutbacks
* Short Term Energy Monitoring: A Road To Long Term Energy Savings?
* NCS-Omnicare: The New Landscape For M&A
* Ohio’s Health House Provides Asthma-Free Indoor Living
* Agistix’s On-Demand Solution Gives Maxim Centralized Logistics Control

(2) Computer Science Department, King Abdullah II School of Information Technology University of Jordan, Amman, Jordan

Corresponding Author: Dr. Hussein Al-Omari, (1) Computer Science Department, School of Computer Science and Information Technology, Applied Science University, Amman, Jordan

Table 1: Jumlah warna di graf yang berbeda di Algoritma yang diimplementasikan

No. of Vertices Density FF LDO IDO

200 25% 20 18 18
200 50% 36 34 34
200 75% 58 55 56
1000 25% 64 62 63
1000 50% 127 123 126
1000 75% 217 212 214

No. of Vertices Proposed SDO Proposed
Algorithm 1 Algorithm 2

200 18 17 16
200 33 32 31
200 55 53 52
1000 62 58 57
1000 122 116 115
1000 211 204 202

Hussein Al-Omari “New graph coloring algorithms”. Journal of Mathematics and Statistics. FindArticles.com. 07 Apr, 2009. http://findarticles.com/p/articles/mi_7039/is_4_2/ai_n28394769/