Yüksek Lisans Tezi

Çizge Algoritmaları ve Çizge Bölmeleme

Ali KARCI

Fırat Üniversitesi

Fen Bilimleri Enstitüsü

Bilgisayar Mühendisliği Anabilim Dalı

1998, Sayfa : 100

Bu çalışmada paralel ortamlarda yük dengeleme şartlarını sağlayacak olan çizge bölmeleme işlemini ve bazı etkili çizge algoritmaların uygulamasını yapan bir yazılım geliştirilmiştir.

Yük dengeleme, paralel ortamlarda her işlemciye mümkünse eşit oranda iş yüklemek ve işlemciler arasındaki iletişimi minimum yapmak olarak tanımlanabilir.

Bu çalışmada ağırlıklı olarak çizge bölmeleme üzerinde durulmuştur. Çizge bölmeleme algoritmaları başlangıçta iki sınıfa ayrılabilir. Eğer çizgenin düğümlerinin koordinatları varsa uygulanan algoritmalar incelenmiştir. Çizgenin düğümlerinin koordinatları yoksa, bu durumda kullanılan algoritmalar incelenmiş ve lineer ve spektral algoritmaların uygulamaları yapılmıştır.

İncelenen yöntemler birbirleri ile kıyaslanarak avantajları ve dezavantajları verilmiştir.

ANAHTAR KELİMELER : Spektral çizge bölmeleme, gelişigüzel çizge bölmeleme, basit çizge indirgeme, çok seviyeli çizge bölmeleme, yük dengeleme, ağ bölmeleme, devre bölmeleme.

TEZE ULAŞABİLMEK İÇİN TIKLAYIN