Publication Type : Conference Paper
Publisher : 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, Bangalore, India.
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
Campus : Amritapuri
School : Department of Computer Science and Engineering, School of Engineering
Department : Computer Science
Year : 2018
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, doi: 10.1109/icacci.2018.8554779.