New Algorithms for Minimum Dominating Set in Any Graphs

Year 2020, Volume: 5 Issue: 2, 62 - 70, 01.12.2020

Ali Karci

Abstract

There are many NP-hard and NP-complete problems in graph theory. The aim of this paper is to solve minimum dominating set problem which is an NP-hard and NP-Complete problem. At this aim, there is a new type spanning tree for given graph, and the fundamental cut-sets of graph are constructed by using this spanning tree. The cut-sets and spanning tree constitute the basic building blocks for algorithms will be proposed in this study.

Keywords

Dominating Sets, Fundamental Cut-Sets, Efficient Algorithms

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., “Efficient Algorithms for Determination of Effective and Ineffective Nodes in Graphs”, Anatolian Science – Journal of Computer Science, 2020.
• 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.