Computing Multiplicative Spanners Efficiently for a Class of Simple Graphs

The notion of a multiplicative t - spanner was defined by David Peleg and Alejandro Scha̅fer in 1989. A vertexspanning sub graph S, of a simple graph H(V, E) in which the pairwise distance between any two vertices is less than or equal to t times that in H is called a puerly multiplicative t - spanner. The real valued parameter t (> 1) denotes the maximum possible multiplicative stretch of u-v distances in the spanner S. Although the combinatorial construction of a t-spanner with m or fewer edges for a given m and t (MTS problem henceforth) is known to be difficult, it is possible to construct MTS efficiently for graphs which satisfies certain properties. In this paper we characterize an infinite family of graph for which the MTS problem can be solved efficiently. Based on the characterization we posit a (n) algorithm for constructing an MTS.