Minimum tepe örtüsü problemi üzerine
On the minimum vertex cover problem
- Tez No: 327269
- Danışmanlar: PROF. DR. URFAT NURİYEV, YRD. DOÇ. DR. MURAT ERŞEN BERBERLER
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 86
Özet
MİNİMUM TEPE ÖRTÜSÜ problemi NP-tam sınıfına ait bir teorik çizge optimizasyon problemidir. Problem bilgisayar bilimlerinde önemli bir rol oynamaktadır ve MİNİMUM TEPE ÖRTÜSÜ örneği olarak formüle edilebilen pek çok gerçek hayat uygulamasına sahiptir. MİNİMUM TEPE ÖRTÜSÜ problemleriyle karşılaşılan uygulama alanlarına örnek olarak iletişim ağları ve özellikle kablosuz ağlar ve bioinformatik verilebilir.MİNİMUM TEPE ÖRTÜSÜ probleminin öneminden dolayı, birçok araştırmacı makul sürelerde kaliteli çözümler veren algoritmalar geliştirmeye odaklanmıştır. Literatürde MİNİMUM TEPE ÖRTÜSÜ problemi için kesin algoritmalar, yaklaşım algoritmaları, sezgisel algoritmalar ve evrimsel algoritmalar dahil bir çok algoritma önerilmiştir.Bu tezde MİNİMUM TEPE ÖRTÜSÜ problemi ele alınmış, problem için geliştirilen çözüm yaklaşımları incelenmiş ve problem için yeni bir sezgisel algoritma ve yeni bir hibrid genetik algoritma önerilmiştir. Önerilen algoritmalar C++ dilinde kodlanmış ve kütüphane örnekleri üzerinde test edilerek literatür çalışmaları ile karşılaştırılmıştır. Hesaplama sonuçları önerilen algoritmaların kaliteli sonuçlar elde ettiğini göstermektedir.
Özet (Çeviri)
THE MINIMUM VERTEX COVER problem is a theoretical graph optimization problem which belongs to the class of NP-complete. The problem plays a central role in computer science and it has a plenty real life applications which can be formulated as instances of the MINIMUM VERTEX COVER. The communication networks, particularly in wireless networks and bioinformatics can be given as examples of such areas where the MINIMUM VERTEX COVER problem occurs.Due to the importance of the MINIMUM VERTEX COVER problem, many researchers have focused on developing algorithms which give quality solutions in a reasonable time. In the literature, there are several algorithm have been proposed for MINIMUM VERTEX COVER problem such as exact algorithms, approximation algorithms, heuristic algorithms and evolutionary algorithms.In this thesis, the MINIMUM VERTEX COVER problem has been studied, the solution approaches for the problem have been investigated, then a new heuristic algorithm and a new hybrid genetic algorithm have been proposed for the problem. The proposed algorithms are the algorithms have been implemented in C++, and have been tested on the benchmark instances, then the results have been compared with studies the literature works. The experimental results show that the proposed algorithms yield quality solutions.
Benzer Tezler
- Minimum tepe örtüsü problemi üzerine
On minimum vertex cover problem
SEMİHA EMİNOĞLU
Yüksek Lisans
Türkçe
2014
MatematikEge ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. ELGİN KILIÇ
PROF. DR. ALPAY KIRLANGIÇ
- Çizge teoride ortalama zedelenebilirlik parametreleri üzerine
On average vulnerability parameters in graph theory
AYŞE TEZEL YOLCU
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
PROF. ERSİN ASLAN
- Güneş lekesi çevrim süreci içerinde kozmik ışınların yeryüzü iklimi-bulut örtüsü ile olan ilişkisinin incelenmesi
The influence of cosmic rays on climate and cloudiness in sunspots cycle
MEHMET ENDER AKCAN
Yüksek Lisans
Türkçe
2004
Meteorolojiİstanbul Teknik ÜniversitesiMeteoroloji Mühendisliği Ana Bilim Dalı
PROF.DR. YURDANUR TULUNAY
Y.DOÇ.DR. SİBEL MENTEŞ
- Amasya Ovası ve yakın çevresinin fiziki coğrafyası
The Geography of physical survey in Amasya plain and its environment
HALİL İBRAHİM ZEYBEK