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

Ali Karcı

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.

Keywords

References

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.

Details

Primary Language

Turkish

Subjects

Software Testing, Verification and Validation

Journal Section

Research Article

Authors

Ali Karcı ^* This is me
Türkiye

Publication Date

December 27, 2020

Submission Date

December 9, 2020

Acceptance Date

December 21, 2020

Published in Issue

Year 2020 Volume: 1 Number: 1

IZ

https://izlik.org/JA55UP44HT

Cite

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 (December 1, 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, vol. 1, no. 1, pp. 16–21, Dec. 2020, [Online]. Available: 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 (December 1, 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, vol. 1, no. 1, Dec. 2020, pp. 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]. 2020 Dec. 1;1(1):16-21. Available from: https://izlik.org/JA55UP44HT