Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme

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.