Improving Greedy Spanner Construction Algorithm

Document Type : Original Article

Authors

• hosein salami
• Mostafa Nouri Baygi

Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

10.22067/cke.2023.73447.1033

Abstract

In recent years, several algorithms with different time complexities have been proposed for the construction of greedy spanners. However, a not so apparently suitable algorithm with running time complexity , namely the FG algorithm, is proved to be practically the fastest algorithm known for this task. One of the common bottlenecks in the greedy spanner construction algorithms is their use of the shortest path search operation (usually using Dijkstra’s algorithm). In this paper, we propose some improvements to the FG algorithm in order to reduce the imposed costs of the shortest path search operation, and therefore to reduce the time required for the construction of greedy spanners. In the first improvement, we reduce the number of this operation calls and in the second one, we reduce the cost of each run of the operation. Experimental results show these improvements are able to significantly accelerate the construction of greedy spanners, compared to the other existing algorithms, especially when the stretch factor gets close to 1.

Keywords

• computational geometry
• greedy spanner
• construction algorithm

Main Subjects

• Computer Science

---

References

• Peleg and A. A. Schäffer, “Graph spanners,” Journal of graph theory, vol. 13, no. 1, pp. 99–116, 1989.
• P. Chew, “There are planar graphs almost as good as the complete graph,” Journal of Computer and System Sciences, vol. 39, no. 2, pp. 205–219, 1989.
• Althöfer, G.  Das, D.  Dobkin, D.  Joseph, and J.  Soares, “On sparse spanners of weighted graphs,” Discrete & Computational Geometry, vol. 9, pp. 81–100, Jan 1993.
• Farshi and J. Gudmundsson, “Experimental study of geometric t-spanners: A running time comparison,” in International Workshop on Experimental and Efficient Algorithms, pp. 270–284, Springer, 2007.
• Bose, P. Carmi, M. Farshi, A. Maheshwari, and M. Smid, “Computing the greedy spanner in near-quadratic time,” Algorithmica, vol. 58, no. 3, pp. 711–729, 2010.
• Bar-On and P. Carmi, “δ-greedy t-spanner,” Computational Geometry 100 (2022): 101807.
• P. Alewijnse, Q. W. Bouts, P. Alex, and K. Buchin, “Computing the greedy spanner in linear space,” Algorithmica, vol. 73, no. 3, pp. 589–606, 2015.
• W. Bouts, A. P. ten Brink, and K. Buchin, “A framework for computing the greedy spanner,” in Proceedings of the thirtieth annual symposium on Computational geometry, pp. 11–19, ACM, 2014.
• P. Alewijnse, Q. W. Bouts, P. Alex, and K. Buchin, “Distribution-sensitive construction of the greedy spanner,” Algorithmica, vol. 78, no. 1, pp. 209–231, 2017.
• Bakhshesh and M. Farshi, “A new construction of the greedy spanner in linear space,” in 1st Iranian Conference on Computational Geometry, pp. 33–36, 2018.
• W. Dijkstra et al., “A note on two problems in connexion with graphs,” Numerische mathematik, vol. 1, no. 1, pp. 269–271, 1959.
• Farshi, and M. J. HekmatNasab. “Greedy spanner algorithms in practice.” Scientia Iranica, vol. 21, no. 6, pp. 2142-2152, 2014.