Geri Dön

Minimum tepe örtüsü problemi üzerine

On the minimum vertex cover problem

  1. Tez No: 327269
  2. Yazar: ONUR UĞURLU
  3. Danışmanlar: PROF. DR. URFAT NURİYEV, YRD. DOÇ. DR. MURAT ERŞEN BERBERLER
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2013
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Minimum tepe örtüsü problemi üzerine

    On minimum vertex cover problem

    SEMİHA EMİNOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    YRD. DOÇ. DR. ELGİN KILIÇ

    PROF. DR. ALPAY KIRLANGIÇ

  2. Çizge teoride ortalama zedelenebilirlik parametreleri üzerine

    On average vulnerability parameters in graph theory

    AYŞE TEZEL YOLCU

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar Üniversitesi

    Yazılım Mühendisliği Ana Bilim Dalı

    PROF. ERSİN ASLAN

  3. 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

    Türkçe

    2004

    Meteorolojiİstanbul Teknik Üniversitesi

    Meteoroloji Mühendisliği Ana Bilim Dalı

    PROF.DR. YURDANUR TULUNAY

    Y.DOÇ.DR. SİBEL MENTEŞ

  4. Balıkesir'de çevre sorunları

    Başlık çevirisi yok

    NECDET EREN

    Yüksek Lisans

    Türkçe

    Türkçe

    1995

    Coğrafyaİstanbul Üniversitesi

    PROF.DR. BARIŞ MATER

  5. 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

    Doktora

    Türkçe

    Türkçe

    1998

    CoğrafyaOndokuz Mayıs Üniversitesi

    Coğrafya Ana Bilim Dalı

    DOÇ. DR. ALİ UZUN