New Algorithms for Minimum Dominating Set in Any Graphs

Ali Karci

New Algorithms for Minimum Dominating Set in Any Graphs

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.

Details

Primary Language

English

Subjects

Computer Software

Journal Section

Research Article

Authors

Ali Karci ^*
Türkiye

Publication Date

December 1, 2020

Submission Date

May 18, 2020

Acceptance Date

June 15, 2020

Published in Issue

Year 2020 Volume: 5 Number: 2

IZ

https://izlik.org/JA74SX57YH

Cite

RIS / Bibtex

APA

Karci, A. (2020). New Algorithms for Minimum Dominating Set in Any Graphs. Computer Science, 5(2), 62-70. https://izlik.org/JA74SX57YH

AMA

1.Karci A. New Algorithms for Minimum Dominating Set in Any Graphs. JCS. 2020;5(2):62-70. https://izlik.org/JA74SX57YH

Chicago

Karci, Ali. 2020. “New Algorithms for Minimum Dominating Set in Any Graphs”. Computer Science 5 (2): 62-70. https://izlik.org/JA74SX57YH.

EndNote

Karci A (December 1, 2020) New Algorithms for Minimum Dominating Set in Any Graphs. Computer Science 5 2 62–70.

IEEE

[1]A. Karci, “New Algorithms for Minimum Dominating Set in Any Graphs”, JCS, vol. 5, no. 2, pp. 62–70, Dec. 2020, [Online]. Available: https://izlik.org/JA74SX57YH

ISNAD

Karci, Ali. “New Algorithms for Minimum Dominating Set in Any Graphs”. Computer Science 5/2 (December 1, 2020): 62-70. https://izlik.org/JA74SX57YH.

JAMA

1.Karci A. New Algorithms for Minimum Dominating Set in Any Graphs. JCS. 2020;5:62–70.

MLA

Karci, Ali. “New Algorithms for Minimum Dominating Set in Any Graphs”. Computer Science, vol. 5, no. 2, Dec. 2020, pp. 62-70, https://izlik.org/JA74SX57YH.

Vancouver

1.Ali Karci. New Algorithms for Minimum Dominating Set in Any Graphs. JCS [Internet]. 2020 Dec. 1;5(2):62-70. Available from: https://izlik.org/JA74SX57YH