- Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi
- Vol: 1 Issue: 1
- Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme
Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme
Authors : Ali Karci
Pages : 16-21
View : 33 | Download : 14
Publication Date : 2020-12-27
Article Type : Research
Abstract :Çizgelerde minimum baskın kümeyi elde etmek NP-Zor problem olup kesin çözümü bulan algoritmanın karmaşıklığı üstel artan bir bağıntıdır. Bu çalışmada minimum baskın kümeyi bulmak amacıyla çizgenin özel bir açılım ağacı elde edilmektedir ve o ağaç kullanılarak temel kesme kümeleri elde edilmektedir. Temel kesme kümeleri ile çizgenin düğüm dereceleri kullanılarak her düğümün baskınlık değeri elde edilir. Minimum baskın kümenin hepsi elde edilinceye kadar bu algoritma tekrar-tekrar uygulanır. Bu çalışmanın katkısı, bu algoritmanın geliştirilmiş olmasıdır.Keywords : Baskın Kümeler, Temel Kesme-Kümeleri, Etkili Algoritmalar