Düğüm Örtüsü Algoritmalarının Performans Değerlendirmesi

Home Page
About
Submit A Journal
Submit A Conference
Submit Paper/Book
- Submit a Preprint
- Submit a Book
Contact

Akademik Bilişim Konferansı
20. AKADEMİK BİLİŞİM KONFERANSI -- AB 2018
Düğüm Örtüsü Algoritmalarının Performans Değerlendirmesi

Düğüm Örtüsü Algoritmalarının Performans Değerlendirmesi

Authors : Yasin Yiğit, Orhan Dağdeviren

Pages : 50-50

View : 57 | Download : 158

Publication Date : 2018-02-02

Abstract :Düğüm örtüsü problemi çizge teorisi alanında sıklıkla çalışılan çok önemli bir problemdir. Ağ bağlantılarının izlenmesi için güvenli noktaların oluşturulması, yolların izlenmesi için kameraların yerleştirilmesi ve filogenetik ağaçların oluşturulması gibi çok önemli uygulama alanları vardır. Düğüm örtüsü problemi NP-ZOR sınıfı içerisinde yer aldığı için bilinen algoritmalar ile polinom zamanda en iyi çözümü bulmak mümkün değildir. Bu sebepten dolayı düğüm örtüsü problemini polinom zamanda çözmek için sezgisel algoritmalar veya yakınsama algoritmaları kullanılmaktadır. Bu çalışmada açgözlü algoritma, 2-yakınsama algoritması ve öz indirgeme yaklaşımını kullanan ve en iyi sonucu veren iki algoritma (VC1 ve VC2) olmak üzere toplam dört algoritmanın teorik ve pratik karşılaştırılması yapılmıştır. Alınan benzetim sonuçlarına göre açgözlü sezgisel algoritma kısa zamanda en iyi sonucu veren algoritmalara yakın sonuçlar vermiştir. Çalışma zamanı açısından, en iyi sonucu veren algoritmalar açgözlü ve 2-yakınsama algoritmasından daha kötü sonuçlar vermiştir. Bunun yanı sıra VC2 algoritmasının VC1 algoritmasına göre 1000 kat daha hızlı çalıştığı gözlemlenmiştir.
Keywords : Düğüm Örtüsü, Sezgisel Algoritmalar, Yakınsama Algoritmaları, En İyi Sonucu Veren Düğüm Örtüsü Algoritmaları

ORIGINAL PAPER URL

* There may have been changes in the journal, article,conference, book, preprint etc. informations. Therefore, it would be appropriate to follow the information on the official page of the source. The information here is shared for informational purposes. IAD is not responsible for incorrect or missing information.