Algorithms for closeness, additional closeness and residual closeness

Journals

Title：
Algorithms for closeness, additional closeness and residual closeness
Author：
Chavdar Dangalchev
Author Affiliation：
Institute of Mathematics and Informatics Bulgarian Academy of Sciences, Sofia, Bulgaria
Received：Mar.3, 2022
Accepted：Mar.22, 2023
Published：Apr.11, 2023

Abstract

The residual and additional closeness are very important characteristics of graphs. They are measures of graphs’ vulnerability and growth potentials. Calculating the closeness, the residual, and the additional closeness of graphs is a difficult computational problem. In this article we propose an algorithm for additional closeness and an approximate algorithm for closeness. Calculating the residual closeness of graphs is the most difficult of the three closenesses. We use Branch and Bound like algorithms to solve this problem. In order for the algorithms to be effective, we need good upper bounds of the residual closeness. In this article we have calculated upper bounds for the residual closeness of 1-connected graphs. We use these bounds in combination with the approximate algorithm to calculate the residual closeness of 1-connected graphs. We have done experiments with randomly generated graphs and have calculated the decrement in steps, delivered by the proposed algorithm.

Keywords

Closeness, residual closeness, additional closeness.

Doi

https://doi.org/10.58396/cvs020102

References

[1] Dangalchev Ch. (2006) Residual closeness in networks. Phisica A. 365:556-564. doi:10.1016/j.physa.2005.12.020.

[2] Dangalchev Ch. (2020) Additional Closeness and Networks Growth. Fundamenta Informaticae. 176(1):1-15. doi:10.3233/FI-2020-1960

[3] Dangalchev Ch. (2022) Additional Closeness of Cycle Graphs. IJFCS. 33(8): 1033-1052. doi:10.1142/s0129054122500149.

[4] Floyd, R.(1962) Algorithm 97: Shortest path. Communications of the ACM, 5(6):345. doi:10.1145/367766.368168

[5] Williams, R. (2014). Faster all-pairs shortest paths via circuit complexity. Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC ’14). New York: ACM. 664–673. doi:10.1145/2591796.2591811.

[6] Thorup, M. (1999). sndirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM. 46(3):362–394. doi:10.1145/316542.316548.

[7] Dangalchev Ch. (2011) Residual closeness and generalized closeness. IJFCS. 22(8):1939-1947. doi:10.1142/s0129054111009136.

[8] Aytac A, Odabas Z.N. (2011) Residual closeness of wheels and related networks. IJFCS. 22(5):1229-1240. doi:10.1142/s0129054111008660.

[9] Odabas Z.N, Aytac A. (2013) Residual closeness in cycles and related networks. Fundamenta Informaticae. 124 (3): 297-307. doi:10.3233/FI-2013-835

[10] Turaci T, Okten M. (2015) Vulnerability of Mycielski graphs via residual closeness, Ars Combinatoria. 118: 419-427.

[11] Aytac A, Berberler Z.N.O. (2017) Robustness of Regular Caterpillars. IJFCS. 28(7): 835-841.

[12] Aytac A, Odabas Z.N. (2017) Network robustness and residual closeness. RAIRO-Operations Research. 52(3), 839-847. doi:10.1051/ro/2016071

[13] Turaci T, Aytac V. (2017) Residual Closeness of Splitting Graphs. Ars Combinatoria. 130: 17-27.

[14] Aytac A, Berberler, Z.N.O. (2017) Residual Closeness for Helm and sunflower graphs. TWMS Journal of applied and Engineering Mathematics. 7(2), 209-220.

[15] Dangalchev Ch. (2018) Residual Closeness of Generalized Thorn Graphs. Fundamenta Informaticae. 162(1), 2018, p 1-15. doi:10.3233/FI-2018-1710

[16] Aytac V, Turaci T. (2018) Closeness centrality in some splitting networks. Computer Science Journal of Moldova. 26(3):251-269.

[17] Berberler ZN, Yigit E. (2018) Link Vulnerability in Networks. IJFCS. 29(03):447-456. doi:10.1142/S0129054118500144

[18] Rupnik D, Zerovnik J. (2019) Networks with Extremal Closeness. Fun- ˇ damenta Informaticae. 167(3):219-234. doi:10.3233/fi-2019-1815.

[19] Yigit E., Berberler ZN. (2019) A Note on the Link Residual Closeness of Graphs snder Join Operation. IJFCS. 30(03):417-424.

[20] Yigit E., Berberler ZN. (2019) Link failure in wheel type networks. IJMPC. 30(09):1-12.

[21] Dangalchev Ch. (2020) Closeness of Splitting Graphs. C.R. Acad. Bulg. Sci. 73(4): 461-466.

[22] B. Zhou, Z. Li, H. Guo. (2021) Extremal results on vertex and link residual closeness. IJFCS. 32:1-21. doi:10.1142/S0129054121500295

[23] Cheng M.Q., Zhou B. (2022) Residual closeness of graphs with given parameters. Journal of the Operations Research Society of China.:1-18. doi:10.1007/s40305-022-00405-9

[24] Wang Y., Zhou B. (2022) Residual Closeness, Matching Number and Chromatic Number. The Computer Journal.. doi:10.1093/comjnl/bxac004

[25] Zheng L., Zhou B. (2022) On the spectral closeness and residual spectral closeness of graphs. RAIRO-Operations Research. 56(4):2651-2668. doi:10.1051/ro/2022125.

[26] G¨olpek H.T. (2022) Vulnerability of Banana trees via closeness and residual closeness parameters. Maltepe Journal of Mathematics. 4(2):1-5. doi:10.47087/mjm.1156370.

[27] Zheng L, Zhou B. (2022) Spectra of closeness Laplacian and closeness signless Laplacian of graphs. RAIRO-Operations Research. 56(5):3525–3543. doi:10.1051/ro/2022161.7