Solving graph partitioning problem using evolutionary heuristic
Çizge parçalama probleminin evrimsel metodla çözülmesi
- Tez No: 75755
- Danışmanlar: DOÇ. DR. FARUK POLAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Çizge Parçalama Problemi, Kenar Çizge Parçalama, Genetik Algoritmalar. IV, Grafik bölümleme, Graph Partitioning, Edge Graph Partitioning, Genetic Algorithms. iii
- Yıl: 1998
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
ABSTRACT SOLVING GRAPH PARTITIONING PROBLEM USING EVOLUTIONARY HEURISTIC Kardaşlar, Murat M.S., Department of Computer Engineering Supervisor: Assoc. Prof. Dr. Faruk Polat August 1998, 74 pages Balanced graph partitioning problem is defined as dividing the vertices of an undirected graph into sets of balanced components through the removal of a set of nodes or edges, whose size are to be minimized. Algorithms that find a good partitioning of undirected graphs are critical for developing efficient solutions for a wide range of problems in many application areas such as, VLSI circuit design, nested dissection algorithm and load balancing in multiprocessor systems. The aim of this work is to present a new genetic algorithm based method for solving the graph partitioning problem through the removal of a set of edges. This method uses a preprocessing method to produce better initial solutions and to speed up the genetic algorithm.
Benzer Tezler
- A Study of optimization problems using neural nets on the transfer
Nöron ağları kullanarak, eniyileme problemlerinin transputer üzerinde incelenmesi
CEVAT ŞENER
Yüksek Lisans
İngilizce
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiYRD. DOÇ. DR. GÜLER MARİFİ
- Grup teknolojisi imalat sistemleri tasarımı için bir metodoloji ve bu metodolojinin endüstride uygulanması
Başlık çevirisi yok
NEVİN AYDIN
Doktora
Türkçe
1998
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. M. BÜLENT DURMUŞOĞLU
- Tek katlı konut tasarımında biçim grameri modeli gecekondu tipi üzerine uygulanması
A Shape grammar model in single storey housign design: Applying to gecekondu type
HÜLYA GÜRPINAR
- Multilevel graph partitioning: An evolutionary approach
Çok seviyeli çizge parçalama: Evrimsel bir yaklaşım
SÜHEYDA KÜÇÜKPETEK
Yüksek Lisans
İngilizce
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
- A Genetic algorithm for graph partitioning
Çizge parçalama problemi için bir genetik algoritma
ESRA AKMAN
Yüksek Lisans
İngilizce
1995
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiY.DOÇ.DR. FARUK POLAT