Teorik Makale
BibTex RIS Kaynak Göster

Calculating the Centrality Values According to the Strengths of Entities Relative to their Neighbours and Designing a New Algorithm for the Solution of the Minimal Dominating Set Problem

Yıl 2023, , 50 - 56, 08.06.2023
https://doi.org/10.53070/bbd.1295038

Öz

The dominating set problem in graph theory is an NP-complete problem for an arbitrary graph. There are many approximation-based studies in the literature to solve the dominating set problems for a given graph. Some of them are exact algorithms with exponential time complexities and some of them are based on approximation without robustness with respect to obtained solutions. In this study, the Malatya centrality value was used and a new Malatya centrality value was defined to solve the dominating set problem for a given graph. The improved algorithms have polynomial time and space complexities.

Kaynakça

  • Bourgeois, N., Croce, F.D., Escoffier, B., Paschos, V.T.,” Fast algorithms for min independent dominating set”, Discrete Applied Mathematics, Vol:161, pp:558-572, 2013.
  • Goddard, W., Henning, M.A.,”Independent domination in graphs: A survey and recent results”, Discrete Mathematics, Vol:313, pp:839-854, 2013.
  • Grandoni, F.,”A note on the complexity of minimum dominating set”, Journal of Discrete Algorithms, Vol:4, pp:209-214, 2006.
  • Guha, S., Khuller, S.,”Approximation Algorithms for Connected Dominating Sets”, Algorithmica, Vol:20, pp:374-387, 1998.
  • Hagerup, T., “A strengthened analysis of an algorithm for Dominating Set in planar graphs”, Discrete Applied Mathematics, Vol:160, pp:793-798, 2012.
  • Karci, A., Yakut, S., Oztemiz, F.,” A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm”, Journal of Computer Science, Vol:7, pp:81-88,2022.
  • Khamis, S.M., Daoud, S.S., Essa, H.A.E,” A randomized algorithm for determining dominating sets in graphs of maximum degree five”, Theoretical Computer Science, Vol:410, pp:5122-5127, 2009.
  • Khuller, S., Yang, S.,” Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm”, Algorithmica, Vol:81, pp:2592-2605, 2019.
  • Van Rooij, J.M.M., Bodlaender, H.L.,” Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.
  • Wawrzyniak, W.,”A local approximation algorithm for minimum dominating set problem in anonymous planar networks”, Distributed Computing, Vol:28, pp:321-331, 2015.

Calculating the Centrality Values According to the Strengths of Entities Relative to their Neighbours and Designing a New Algorithm for the Solution of the Minimal Dominating Set Problem

Yıl 2023, , 50 - 56, 08.06.2023
https://doi.org/10.53070/bbd.1295038

Öz

The dominating set problem in graph theory is an NP-complete problem for an arbitrary graph. There are many approximation-based studies in the literature to solve the dominating set problems for a given graph. Some of them are exact algorithms with exponential time complexities and some of them are based on approximation without robustness with respect to obtained solutions. In this study, the Malatya centrality value was used and a new Malatya centrality value was defined to solve the dominating set problem for a given graph. The improved algorithms have polynomial time and space complexities.

Kaynakça

  • Bourgeois, N., Croce, F.D., Escoffier, B., Paschos, V.T.,” Fast algorithms for min independent dominating set”, Discrete Applied Mathematics, Vol:161, pp:558-572, 2013.
  • Goddard, W., Henning, M.A.,”Independent domination in graphs: A survey and recent results”, Discrete Mathematics, Vol:313, pp:839-854, 2013.
  • Grandoni, F.,”A note on the complexity of minimum dominating set”, Journal of Discrete Algorithms, Vol:4, pp:209-214, 2006.
  • Guha, S., Khuller, S.,”Approximation Algorithms for Connected Dominating Sets”, Algorithmica, Vol:20, pp:374-387, 1998.
  • Hagerup, T., “A strengthened analysis of an algorithm for Dominating Set in planar graphs”, Discrete Applied Mathematics, Vol:160, pp:793-798, 2012.
  • Karci, A., Yakut, S., Oztemiz, F.,” A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm”, Journal of Computer Science, Vol:7, pp:81-88,2022.
  • Khamis, S.M., Daoud, S.S., Essa, H.A.E,” A randomized algorithm for determining dominating sets in graphs of maximum degree five”, Theoretical Computer Science, Vol:410, pp:5122-5127, 2009.
  • Khuller, S., Yang, S.,” Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm”, Algorithmica, Vol:81, pp:2592-2605, 2019.
  • Van Rooij, J.M.M., Bodlaender, H.L.,” Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.
  • Wawrzyniak, W.,”A local approximation algorithm for minimum dominating set problem in anonymous planar networks”, Distributed Computing, Vol:28, pp:321-331, 2015.
Toplam 10 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Bilgisayar Yazılımı, Yazılım Testi, Doğrulama ve Validasyon
Bölüm PAPERS
Yazarlar

Şeyda Karcı 0000-0001-8489-7828

Fatih Okumuş 0000-0003-3046-9558

Ali Karci 0000-0002-8489-8617

Erken Görünüm Tarihi 8 Haziran 2023
Yayımlanma Tarihi 8 Haziran 2023
Gönderilme Tarihi 14 Mayıs 2023
Kabul Tarihi 2 Haziran 2023
Yayımlandığı Sayı Yıl 2023

Kaynak Göster

APA Karcı, Ş., Okumuş, F., & Karci, A. (2023). Calculating the Centrality Values According to the Strengths of Entities Relative to their Neighbours and Designing a New Algorithm for the Solution of the Minimal Dominating Set Problem. Computer Science, Vol:8(Issue:1), 50-56. https://doi.org/10.53070/bbd.1295038

The Creative Commons Attribution 4.0 International License 88x31.png  is applied to all research papers published by JCS and

a Digital Object Identifier (DOI)     Logo_TM.png  is assigned for each published paper.