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

Ali Karcı

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

Ö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

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.

Ayrıntılar

Birincil Dil

Türkçe

Konular

Yazılım Testi, Doğrulama ve Validasyon

Bölüm

Araştırma Makalesi

Yazarlar

Ali Karcı ^* Bu kişi benim
Türkiye

Yayımlanma Tarihi

27 Aralık 2020

Gönderilme Tarihi

9 Aralık 2020

Kabul Tarihi

21 Aralık 2020

Yayımlandığı Sayı

Yıl 2020 Cilt: 1 Sayı: 1

IZ

https://izlik.org/JA55UP44HT

Kaynak Göster

RIS / Bibtex

APA

Karcı, A. (2020). Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 1(1), 16-21. https://izlik.org/JA55UP44HT

AMA

1.Karcı A. Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2020;1(1):16-21. https://izlik.org/JA55UP44HT

Chicago

Karcı, Ali. 2020. “Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme”. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 1 (1): 16-21. https://izlik.org/JA55UP44HT.

EndNote

Karcı A (01 Aralık 2020) Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 1 1 16–21.

IEEE

[1]A. Karcı, “Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme”, Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, c. 1, sy 1, ss. 16–21, Ara. 2020, [çevrimiçi]. Erişim adresi: https://izlik.org/JA55UP44HT

ISNAD

Karcı, Ali. “Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme”. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 1/1 (01 Aralık 2020): 16-21. https://izlik.org/JA55UP44HT.

JAMA

1.Karcı A. Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2020;1:16–21.

MLA

Karcı, Ali. “Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme”. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, c. 1, sy 1, Aralık 2020, ss. 16-21, https://izlik.org/JA55UP44HT.

Vancouver

1.Ali Karcı. Minimum Baskın Küme Problemini Polinomsal Yöntemle Çözme. Muş Alparslan Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi [Internet]. 01 Aralık 2020;1(1):16-21. Erişim adresi: https://izlik.org/JA55UP44HT