Düğüm Örtüsü Algoritmalarının Performans Değerlendirmesi
AbstractDüğü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.