A Genetic algorithm for graph partitioning

---

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: 1995

Tezin Dili: İngilizce

Öğrenci: ESRA AKMAN

Danışman: FARUK POLAT

Özet:

Öz ÇİZGE PARÇALAMA İÇİN BİR GENETİK ALGORİTMA Akman, Esra Yüksek Lisans, Bilgisayar Mühendisliği Bölümü Tez Yöneticisi: Y. Doç. Dr. Faruk Polat Temmuz 1995, 90 sayfa Çizge (Graph) Parçalama Problemi önemli bir çizge kuramsal problemdir. Problem, yönlendirilmemiş bir çizgenin mümkün olan en az sayıda düğüm (node) yada kenar (edge) çıkarımıyla, iki dengeli parçaya bölünmesi olarak tanımlanabilir. Problemin çözümü, Çok Geniş Ölçekli Tümleşik devre tasarımı, çok işlemcili sis temlerde yük dengelemesi ve içice bölme algoritması gibi birçok problemin etkin çözümü için önem taşımaktadır. Bu çalışmada amaçlanan çizge parçalama problemini düğüm kümesi çıkarımıyla çözebilen yeni bir metod sunmaktır. Bu yeni metod genetik algoritma esasına dayanmaktadır. Anahtar Kelimeler: Çizge Kuramı,Çizge Parçalama Problemi, Düğümsel Çizge Parçalama, Genetik Algoritmalar