Publication Type : Conference Paper
Publisher : 2018 International Conference on Data Science and Engineering (ICDSE)
Source : 2018 International Conference on Data Science and Engineering (ICDSE), IEEE, Kochi, India (2018)
ISBN : 9781538648551
Keywords : Clustering algorithms, combinatorial construction, Complexity theory, Computational complexity, Computer science, computing multiplicative spanners, Data Science, Graph algorithms, Graph Spanner, Graph theory, Image segmentation, MTS problem, multiplicative t - spanner, NP Hard optimization, Pairwise distance, Partitioning algorithms, vertex spanning sub graph, Wireless sensor networks
Campus : Amritapuri
School : Department of Computer Science and Engineering, School of Engineering
Department : Computer Science
Year : 2018
Abstract : 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.
Cite this Research Publication : Y. Veluri, Jayakumar P., and Nair, J. J., “Computing Multiplicative Spanners Efficiently for a Class of Simple Graphs”, in 2018 International Conference on Data Science and Engineering (ICDSE), Kochi, India, 2018