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

Yıl 2020, Cilt: 1 Sayı: 1, 16 - 21, 27.12.2020

Ali Karcı

https://izlik.org/JA55UP44HT

Öz

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

Anahtar Kelimeler

Baskın Kümeler , Temel Kesme-Kümeleri , Etkili Algoritmalar

Kaynakça

• Alikhan, S., Peng, Y.-H., “Construction of Dominating Sets of Certain Graphs”, Journal of Discrete Mathematics, Vol:2013, Article ID:587196, 2013.
• Bresar, B., Movarraei, N., “On the number of maximal independent sets in minimum colorings of split graphs”, Discrete Applied Mathematics, Vol:247, pp:352-356, 2018.
• Connolly, S., Gabor, Z., Godbole, A., Kay, B., Kelly, T.,”Bounds on the Maximum Number of Minimum Dominating Sets”, Discrete Mathematics, Vol:339, pp:1537-1542, 2016.
• Deng, Y.-P., Sun, Y.-Q., Liu, Q., Wang, H.-C.,”Efficient Dominating Sets in Circular Graphs”, Discrete Mathematics, Vol:340, pp:1503-1507, 2017.
• Goddard, W., Henning, M.A., “Independent domination in Graphs: A Survey and Recent Results”, Discrete Mathematics, Vol: 313, pp:839-854, 2013.
• Golovach, P.A., Heggernes, P., Kante, M.M., Kratsch, D., Villanger, Y.,”Enumerating Minimal Dominating Sets in Chordal Bipartite Graphs”, Discrete Applied Mathematics, Vol:199, pp:30-36, 2016.
• Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
• Karci, A., “Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science – Journal of Computer Science, Vol:5, pp:137-143, 2020a.
• Karci, A., “New Algorithms for Minimum Dominating Set in Any Graphs”, Anatolian Science – Journal of Computer Science, Vol:5, pp:62-70, 2020b.
• Marti-Farre, J., Mora, M., Ruiz, J. L.,”Uniform Clutters and Dominating Sets of Graphs”, Discrete Applied Mathematics, Vol:263, pp:220-233, 2019.
• Rooij, J.van, Bodlaender, H.L., “Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.