Construction of Multiplicative Graph Spanners using Minimum Connected Dominating Set with Bounded Diameter

摘要

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.}