Research Article
Year 2020,
Volume: 5 Issue: 2, 62 - 70, 01.12.2020
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.
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.
Year 2020,
Volume: 5 Issue: 2, 62 - 70, 01.12.2020
Abstract
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.
There are 10 citations in total.
Details
| Primary Language | English |
|---|---|
| Subjects | Computer Software |
| Journal Section | PAPERS |
| Authors | |
| Publication Date | December 1, 2020 |
| Submission Date | May 18, 2020 |
| Acceptance Date | June 15, 2020 |
| Published in Issue | Year 2020 Volume: 5 Issue: 2 |
The Creative Commons Attribution 4.0 International License
is applied to all research papers published by JCS and
A Digital Object Identifier (DOI) 
is assigned for each published paper.