It’s me, live with it

Well, another music video post. This time it’s a korean boyband that got me somewhat curious after watching Family Outing. It’s pretty darn awesome.

Well, I’ve been using intel for quite a while now, starting with a 2,66GHz prescott, to a Pentium D 925, and now an e2180. I used to use a celeron 400 and a Pentium III, too, so the name ‘pentium’ is carved strongly inside my head.

Nowadays, intel’s “pentium” lineup is filled with cut down core 2 processors, which is not a bad thing, but might be confusing. I’ll take a pentium e6300 for example. Not only it shares a name with a core 2 processor, named appropriately core 2 duo e6300. I’m willing to bet that it perform much better than its core 2 brother. Heck, I’d bet it trade blows evenly with a core 2 duo e7300 in raw power. The pentium e6300 even has Intel Virtualization Technology listed as a feature, which should make it perform better than the e7300 in virtualization tasks.

Anyway, now that intel have pretty much released a very awesome dual core processor for its price (About US$82 in US, maybe IDR 1 million here), I wonder whether they will release a pentium Quad core.

Intel’s Quad core lineup starts with q6600 and q8200 up to the Holy-crap-look-at-the-price core i7 975.

The cheapest Intel Quad core processor you can find now is the q8200, which can be had for around IDR 1,7 million. Not exactly expensive, but not really affordable either. Which got me thinking, why don’t they release a cheap, cut down quad core processor and name them ‘Pentium Quad Core’?

I don’t think it’s a bad idea. Intel’s pentium dual core processors are very competitive, even the slowest pentium dual core you can find now, the e2160, should give you enough performance to do most tasks with reasonable speed, even including gaming.

Which is why I think that a 2 GHz pentium quad core might not be a bad idea, they can cut the cache to around 4 megabyte and lower the price to a more affordable level of, say, IDR 1 million, at which we can find AMD’s triple-core phenom. The pentium should have lower power consumption than the phenom, and, in quad-core optimized applications, faster. A 2 GHz core microarchitecture processor shouldn’t be a slouch in single-core-only applications either.

If at future time intel release something like a ‘Pentium quad core q7200′, I will want my part.

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

A PARALLEL MERGING ALGORITHM AND ITS IMPLEMENTATION WITH JAVA THREADS
ALGORITMA MERGE PARALLEL DAN IMPLEMENTASIYA DENGAN JAVA THREAD

SOWMYA PRABHA NAGARAJA sowmyaprabha@yahoo.com
YUAN PAN yuanpan33@usa.net
MEHDI BADII mbadii@pace.edu
Pace University,
Pleasantville, NY

Keberhasilan ilmu komputer untuk menjelaskan secara akurat dan memodelkan dunia nyata telah mendorong permintaan akan komputasi murah. Ilmuwan terus mencari cara untuk menguji batas teori, menggunakan komputasi kinerja tinggi untuk mengizinkan mereka untuk mensimulasikan sistem lebih realistis dengan lebih detail. Komputasi paralel menawarkan cara untuk menanggulangi masalah ini dengan biaya efektif.

Salah satu alasannya merupakan alasan ekonomi. Dengan membuat penggunaan komponen “off the shelf”, komputer paralel dapat menawarkan kinerja tinggi dengan harga lebih rendah daripada mesin yang menggunakan prosesor yang khusus. Selain itu, skalabilitas dari komputer paralel memungkinkan mereka untuk ditingkatkan sebagai kebutuhan. Dimana pada arsitektur seri upgrade prosesor adalah dengan menjadikan prosesor sebelumnya usang, arsitektur paralel dapat, secara teori, ditingkatkan dengan menambah prosesor lagi.

Namun demikian, ada alasan lain, dasar hukum fisik, yang pada akhirnya akan membatasi kecepatan prosesor tunggal, yang terlepas dari ekonomi. Gerakan informasi merupakan bentuk dasar dari komputer, tetapi kecepatan ini pada akhirnya dibatasi oleh kecepatan cahaya. Jika bukan jarak dijalani oleh informasi ini berkurang, akhirnya kebutuhan untuk menghindari ketidakpastian diperkenalkan oleh kuantum mekanik akan membatasi perpecahan di sepanjang jalan yang dapat dijalani oleh informasi.

Kedua alasan perekonomian dan fisika, digabungkan dengan skalabilitas yang melekat pada komputer paralel, mengarah ke masa depan komputasi performa tinggi yang didasarkan pada beberapa jalan pada ide dari parallelism.

Banyak pekerjaan telah dilakukan dalam bidang ini menggunakan berbagai teknik. Untuk contoh,

1. algoritma pada distribusi memori komputer asynchronous[1] dimana algoritma mengurangi biaya operasi yang menggabungkan dan komunikasi, serta sebagian memecahkan masalah load balancing,
2. metodologi untuk memprediksi kinerja algoritma paralel pada komputer paralel[2]. Metodologi ini terdiri dari dua langkah.Perrtama, mesin dikarakterisasikan dengan mengenumerasikan primitif operasi yang mampu melakukan bersama biaya operasi masing-masing. Selanjutnya, adalah suatu algoritma dianalisa oleh membuat tepat hitungan jumlah kali algoritma melakukan tiap jenis operasi.
3. Penyortiran paralel menurut Overpartitioning [3] - Pendekatan ini membatasi biaya komunikasi
   bergerak oleh setiap elemen antara prosesor paling banyak sekali, dan mengarah ke balancing dengan probabilitas tinggi.

Analisis Algoritma Paralel
Analisis algoritma merujuk kepada proses penentuan bagaimana suatu algoritma yang baik, yaitu bagaimana cepat, seberapa mahal untuk berjalan, dan seberapa efisien dalam penggunaan sumber daya yang tersedia. Begitu algoritma untuk beberapa masalah telah dirancang, biasanya dievaluasi dengan menggunakan kriteria sebagai berikut: running time, jumlah prosesor yang digunakan, dan biaya. Selain standar metrik ini, sejumlah teknologi lainnya terkait langkah-langkah yang terkadang digunakan ketika diketahui bahwa algoritma ini telah berjalan pada komputer yang didasarkan pada teknologi tertentu.

Sejak mempercepat perhitungan menjadi alasan utama di belakang kami dalam membangun paralel komputer, ukuran yang paling penting dalam mengevaluasi sebuah algoritma paralel karena itu dengan running time (n). Ini didefinisikan sebagai waktu yang diambil oleh algoritma untuk memecahkan masalah pada komputer paralel, yang berlalu dari saat algoritma mulai hingga berakhir.

Kedua kriteria paling penting dalam mengevaluasi sebuah algoritma paralel adalah jumlah prosesor yang diperlukan untuk memecahkan masalah.

Biaya algoritma paralel didefinisikan sebagai produk dari dua tindakan sebelumnya, maka
Biaya = paralel waktu berjalan * jumlah prosesor yang digunakan
i.e. c (n) = p (n) * t (n)
dimana p (n) adalah jumlah prosesor dan t (n) adalah running time paralel

Disamumsikan bahwa batas bawah terikat pada jumlah yang diperlukan dalam operasi berurut dalam worst case untuk memecahkan masalah. Jika algoritma paralel yang cocok untuk masalah ini biaya pasti akan lebih rendah dalam multiplicative faktor konstan, maka algoritma adalah biaya yang optimal. J paralel algoritma biaya tidak optimal jika berurut algoritma yang ada saat ini berjalan lebih kecil dibandingkan dengan biaya algoritma paralel.

Pendekatan Konseptual Kami

Bagus untuk menerapkan model arsitektur parallelism yang dapat diskala, setidaknya pada prinsipnya, sebagai masalah ukuran meningkat. Parallelism yang didukung oleh arsitektur ini adalah eksplisit dalam arti bahwa biasanya mereka secara eksplisit mendukung sebuah model pemrograman paralel. Arsitektur model ini telah diklasifikasikan bersama berbagai axes: SIMD atau MIMD, bersama memori-memori atau didistribusikan, untuk tujuan umum atau khusus, digabungkan dengan longgar atau ketat, penggunaan interkoneksi jaringan statis versus dinamis , dll.

Karya ini berkaitan dengan menggabungkan algoritma paralel. Algoritma yang asli dirancang untuk CREW SM SIMD komputer. SIMD arsitektur terdiri dari kumpulan prosesor homogen yang menjalankan instruksi secara bersamaan pada berbagai item data. Arsitektur SIMD akan sangat efisien untuk komputasi reguler pada kumpulan data besar sebagai typified oleh matriks computations padat. Karena arsitektur SIMD memiliki satu tempat program kontrol, desain dan debugging program maka biasanya lebih mudah daripada untuk arsitektur MIMD. Dengan demikian, keuntungan utama dari model ini yang kedua adalah hardware dan software desain masalah yang relatif sederhana.

Algoritma ini ditingkatkan dan dilaksanakan dengan fitur Multithreading Java. Yang dikehendaki
dari menggabungkan algoritma paralel, seperti jumlah thread yang digunakan oleh algoritma, adalah sub linear dan adaptif. Waktu running dari algoritma secara signifikan lebih kecil dibandingkan dengan algoritma berurut. Biaya dari algoritma yang optimal.

Untuk dua sequence diurutkan dari ukuran r dan s, dan dalam kasus terburuk di mana r = s = n, waktu putar O ((n / N) + log n), dimana N merupakan jumlah thread. Algoritma adalah biaya yang optimal untuk N = n / log n.

Pelaksanaan kami dan Algoritma
Pelaksanaan kami memiliki delapan kelas Java:

1. Main - Menciptakan yang dimulai N threads
2. Generator - mempopulasikan 2 array yang harus digabungkan dengan menghasilkan nomor acak
3. MyThread - kelas dimana semua pekerjaan dilakukan seperti yang dijelaskan di bawah
4. Pasangan - pasangan lain yang dijelaskan pada langkah 3 di bawah
5. Tripel - menghasilkan triples dijelaskan pada Langkah 2 di bawah
6. Printer - cetak output yaitu array yang telah digabung ke file
7. Sorter - dua jenis input non array dalam urutan atas ke bawah
8. Waiter - ini adalah kelas di mana semua thread menunggu

Algoritma
Biarkan A dan B yang akan diberikan array bersama dengan masing-masing elemen r dan s, diurutkan di
urutan nondecrease. Hal ini diperlukan untuk menggabungkan mereka ke dalam array C.
Seperti disajikan oleh Akl [4], maka algoritma adalah sebagai berikut:

Langkah 1: Algoritma memilih N-1 elemen dari array A untuk bersama array J ‘. J ini membagi N kira-kira sama dalam ukuran segmen. J bersama array B ‘N-1 elemen B juga dipilih. Untuk langkah ini, setiap Pi penyisipan J [i * r / N] dan B [i * r / N] secara paralel ke dalam i lokasi A dan B ‘ masing-masing.

Langkah 2: Langkah ini menggabungkan A dan B ‘menjadi deret bersama V ukuran 2n - 2. Setiap elemen v V merupakan triple terdiri dari elemen A ‘atau B’ diikuti oleh posisinya dalam A ‘atau B’ diikuti oleh nama A atau B.

Untuk langkah ini setiap Pi:
a. Berurut menggunakan prosesor Binary CARI setiap pencarian di array B ’secara paralel untuk menemukan seperti yang terkecil j A ‘[i] < b ' [j]. J jika ada, maka V [i + j -1] diatur oleh triple (A '[i], i, "A"),
lain V [i + N -1] diatur oleh triple (A '[i], i, "A").
b. Berurut menggunakan prosesor Binary CARI setiap pencarian yang array A 'untuk menemukan j terkecil seperti yang B '[i] < a [j]. J jika ada, maka V [i + j -1] ditentukan oleh tiga
(B '[i], i, "B"), jika V [i + N -1] ditentukan oleh tiga (B' [i], i, "B").

Langkah 3: Untuk menggabung A dan B dibagi menjadi array C, dengan indeks dari dua elemen (satu di A dan satu di B) di mana setiap prosesor adalah untuk mulai yang menggabungkan computed bersama dalam array T yang memerintahkan pasangan. Langkah ini dijalankan sebagai berikut:
a. P1 set T [1] oleh (1,1).
b. Setiap Pi, i> = 2, memeriksa apakah V [2i -2] adalah sama dengan (A [k], k, “A”) atau tidak. Jika sama maka pencarian Pi B
menggunakan Binary CARI untuk menemukan j terkecil seperti yang B [j]> A [k] dan set T [i] oleh (k * r / N, j),
lain J Pi pencarian menggunakan Binary CARI untuk menemukan j terkecil sedemikian rupa sehingga
J [j]> B ‘[k] dan set T [i] oleh (j, k * s / N).

Langkah 4: Masing-masing Pi, i dua subarrays J [x.. u-1] dan B [y.. v-1] dan tempat hasil dalam menggabungkan array C di posisi x + y - 1. PN menggunakan prosesor T [N] = (w, z) untuk menggabungkan dua subarrays J [w.. R] dan B [Z.. S].

Perbaikan kami ke Algoritma
Kami telah membuat perbaikan berikut pada algoritma:
(a). Set N = minimum (r, s, p), di mana r, s, dan p adalah ukuran array A, B, dan jumlah prosesor di
sistem masing-masing. Asumsi ini menjamin bahwa jumlah prosesor yang tidak lebih besar dari ukuran setiap array. Mengubah nama "berurut Bergabung" ke "Teruskan berurut Bergabung" dan menentukan "Mundur berurut Bergabung" untuk menggabung dua subsequences dari ujung kanan subsequences.
(b). Pada langkah 4, setelah prosesor Pi merges nya subsequences, ia menemukan sibuk Pk prosesor, dan panggilan "MundurBerurut Bergabung "untuk menggabungkan subsequences dari Pk dari hak mereka berakhir, sementara Pk mereka adalah menggabungkan
dari kiri berakhir.

Analisis dari Algoritma

Meskipun kami telah meliputi penyortiran prosedur dalam program kami, kami tidak akan menyertakan analisis yang langkah karena fokus pada adalah menggabungkan dua array diurutkan. Prosedur sorting yang disertakan hanya untuk memberikan ketidaktetapan untuk seluruh program tersebut.

Langkah 1: Semua prosesor beroperasi secara paralel. Setiap prosesor computes dua subscripts; maka ini
langkah memerlukan waktu konstan.
Langkah 2: Langkah ini terdiri dari dua berurut Binary CARI prosedur diterapkan ke urutan
panjang dari N-1. Sebuah pernyataan berikut tugas masing-masing prosedur. Hal ini memakan waktu O (log N) waktu.
Langkah 3: Langkah 3 (a) terdiri dari konstan-waktu tugas.
Langkah 3 (b) paling banyak membutuhkan O (log s) waktu.
Langkah 4: Pengamatan: --
Array yang berisi 2n V - 2 unsur yang memisahkan C menjadi 2n - 1 dengan subsequences Ukuran maksimum sebesar (r / N + s / N). Ukuran maksimum ini terjadi jika, misalnya, satu dari unsur a'i A 'sama dengan sebuah elemen b'j dari B'. Maka r / N elemen kecil dari atau sama dengan a'i (dan lebih besar daripada
atau sama dengan a'i-1) juga lebih kecil dari atau sama dengan b'j. Demikian pula s / N elemen atau lebih kecil daripada setara dengan b'j (dan lebih besar dari atau sama dengan b'j, dan b'j-1) juga lebih kecil dari atau sama dengan a'i. Pada langkah 4 setiap dua prosesor menciptakan seperti subsequences C yang jumlah ukuran tidak lebih besar dari 2 (r / N + s / N),
kecuali PN, yang hanya menciptakan satu subsequence dari C. Penyalahgunaan berikut bahwa berurut Bergabung prosedur yang memakan waktu paling banyak O ((r + s) / N) waktu.

Pada kasus terburuk, r = s = n. Sejak n> = N, yang menjalankan algoritma dari waktu didominasi oleh
waktu yang diperlukan oleh Langkah 3 dan 4. Jadi

t (2n) = O ((n / N) + log n)

Sejak p (2n) = N, c (2n) = p (2n) * t (2n) = O (n + Nlogn), dan algoritma adalah biaya yang optimal ketika
N < = n / logn.

Kesimpulan

Tidak adanya komputer multiprocessor di lembaga ini bukan merupakan kendala dalam penelitian melibatkan algoritma paralel karena kita dapat menggunakan teknik seperti Multithreading yang tersedia dalam bahasa pemrograman seperti bahasa Java atau menggunakan simulator tersedia untuk algoritma paralel [5] di mana fungsi-fungsi simulator membolehkan programmer untuk menangani komunikasi dan sinkronisasi kebutuhan satu algoritma di tingkat yang lebih tinggi daripada sistem UNIX multiprocessing panggilan, sementara berkonsentrasi pada desain yg berbarengan
algoritma. Anyhow, juga memungkinkan untuk menggunakan sistem seperti panggilan tunggu dan sinyal dalam UNIX untuk tujuan ini [6].

References

[1] Efficient Implementation of Sorting Algorithms on Asynchronous Distributed-Memory Machine
(1993)
Zhou B. B., Brent R. P. and Tridgell A. Computer Sciences Laboratory. The ICPADS: International
Conference on Parallel and Distributed Systems, National Tsing Hua University, Hsinchu, Taiwan,
Republic of China
[2] An Experimental Analysis of Parallel Sorting Algorithms (1998)
Guy E. Blelloch Carnegie Mellon University Pittsburgh, PA 15213 C. Greg. Theory of Computing System
[3] Parallel Sorting by Overpartitioning (1994)
Hui Li and Kenneth C. Sevcik February 1994 Computer Systems Research.SPAA: Annual ACM
Symposium on Parallel Algorithms and Architectures
[4] The Design and Analysis of Parallel Algorithms (1989)
Selim G. Akl Prentice Hall, Inc.
[5] Simulating the DYNIX Operating System Parallel Programming Interface on a UNIX System
(1998)
M. Badii, Sofrware-Practice and Experience, Vol. 28(5), 463-480 (998)
[6] Dataflow Simulator
M. Badii and M. Mahimtura. Proceedings of Tenth Annual ESCC Conference, October 21-22 1994.

Jurnal Original:
http://www.research.ibm.com/masplas/masplas01/nagaraja.pdf

Everyone that make software agree that publishing their software in a P2P site is a bad thing. It’s practically stealing their hours of building it. And I’m not just talking about the legit software company. Heck, look at this screenshot:

Yeah, that is RELOADED, complaining about P2P users publishing their crack.

Granted, they seems like the lone, hated group from the scene, but still, They worked for their release, and pissed of when someone put them on P2P.

I’m kinda shocked about this. For all these years of seeing (and using) cracks and fixes made by them, I thought they are the one who put it on P2P. I guess I was wrong, then.

Which brings us to today’s topic: What can you do if you can’t pay for your softwares?

Well, you can always use free software (both as in beer and as in speech). There should be almost anything you need in the free world. Need a good OS? Linux, or BSD should do fine. Word Processors? Openoffice, KOffice, Gnome Office, LaTeX will do all of them. Multimedia? A lot of choice you can choose from.

Most of the software I mentioned above can be had for nothing. You can use it as you like, get a free community support, free updates, and you can freely redistribute it, Like selling your own PC brand with free software loaded into them.

But is that it? You use the software, made money with it, and walk away?

Let’s not do that, shall we?

There are a LOT of ways for you to return what free software gave you. For example, you can hang out at the community forum, providing support for others, you can help translate the software, you can help track their bugs, and, of course, you can help them build it.

To give and to receive is a beautiful thing.

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/