TY  - JOUR
TT  - New Algorithms for Minimum Dominating Set in Any Graphs
AU  - Karci, Ali
PY  - 2020
DA  - December
Y2  - 2020
JF  - Computer Science
JO  - JCS
PB  - Ali KARCI
WT  - DergiPark
SN  - 2548-1304
SP  - 62
EP  - 70
VL  - 5
IS  - 2
LA  - en
KW  - Dominating Sets
KW  - Fundamental Cut-Sets
KW  - Efficient Algorithms
N2  - 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.
CR  - Alikhan, S., Peng, Y.-H., “Construction of Dominating Sets of Certain Graphs”, Journal of Discrete Mathematics, Vol:2013, Article ID:587196, 2013.
CR  - 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.
CR  - 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.
CR  - 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.
CR  - Goddard, W., Henning, M.A., “Independent domination in Graphs: A Survey and Recent Results”, Discrete Mathematics, Vol: 313, pp:839-854, 2013.
CR  - 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.
CR  - Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
CR  - Karci, A., “Efficient Algorithms for Determination of Effective and Ineffective Nodes in Graphs”, Anatolian Science – Journal of Computer Science, 2020.
CR  - Marti-Farre, J., Mora, M., Ruiz, J. L.,”Uniform Clutters and Dominating Sets of Graphs”, Discrete Applied Mathematics, Vol:263, pp:220-233, 2019.
CR  - Rooij, J.van, Bodlaender, H.L., “Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.
UR  - https://dergipark.org.tr/tr/pub/bbd/issue//739158
L1  - https://dergipark.org.tr/tr/download/article-file/1109066
ER  -