© Amrita Vishwa Vidyapeetham Amritapuri | Bengaluru | Chennai | Coimbatore | Kochi | Mysuru
A Multiplicative Spanner is a spanning sub-graph H(V, E') of a graph G(V, E) such that where distance(u, v, G) is the shortest distance between the vertices u and v in G. The parameter t is called the multiplicative stretch of the spanner. When the size of the graph is reduced to construct a spanner, the shortest distance between the vertices increases, consequently the stretch factor also increases. It is known that the construction of spanners with optimum size-stretch is hard. Many researchers proposed efficient algorithms that yield proven near optimal results. In this paper we propose a quadratic time algorithm to construct multiplicative t-spanners with a bound on the stretch factor.
P. Tatikonda, Kuppili, H., Paila, A., Pail, J., and Jayakumar P., “Construction of Multiplicative Graph Spanners using Minimum Connected Dominating Set with Bounded Diameter”, in 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Bangalore, India, 2018.