Publication Type:

Conference Paper

Source:

2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, Bangalore, India (2018)

URL:

https://ieeexplore.ieee.org/document/8554779

Keywords:

Additives, Approximation algorithms, Clustering algorithms, Computer science, Connected dominating sets, Diameter of a Graph, Fault tolerance, Fault tolerant systems, Graph Spanner, Graph theory, Maximal Independent set, minimum connected dominating set, multiplicative graph spanners, multiplicative stretch, multiplicative t-spanners, optimum size-stretch, Partitioning algorithms, Set theory, shortest distance, spanning sub-graph, stretch factor

Abstract:

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.

Cite this Research Publication

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.