Solving graph partitioning problem using evolutionary heuristic

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 1998

Tezin Dili: İngilizce

Öğrenci: MURAT KARDAŞLAR

Danışman: FARUK POLAT

Özet:

oz ÇİZGE PARÇALAMA PROBLEMİNİN EVRİMSEL METODLA ÇÖZÜLMESİ Kardaşlar, Murat Yüksek Lisans, Bilgisayar Mühendisliği Bölümü Tez Yöneticisi: Doç. Dr. Faruk Polat Ağustos 1998, 74 sayfa Dengeli çizge parçalama problemi yönlendirilmemiş bir çizgenin mümkün olan en az sayıda düğüm ya da kenar çıkarımıyla, dengeli parçalara bölünmesidir. Yönlendirilmemiş çizgeleri iyi bölen algoritmaların kullanımı Çok Geniş Ölçekli Tümleşik devre tasarımı, içice bölme algoritması, çok işlemcili sistemlerde yük dengelemesi gibi çok çeşitli problemlerin verimli olarak çözülebilmesinde önem taşımaktadır. Bu çalışmada amaçlanan, çizge parçalama problemini kenar kümesi çıkarımıyla çözebilen ve genetik algoritmalara dayanan bir metod sunmaktır. Bu metod daha iyi başlangıç çözümleri üretmek ve genetik algoritmayı hızlandırmak için bir önişlem uygulamaktadır. Anahtar Kelimeler: Çizge Parçalama Problemi, Kenar Çizge Parçalama, Genetik Algoritmalar. IV