Publisher : 2017 International Conference on Advances in Computing, Communications and Informatics
Source : 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, Udupi, India (2017)
Url : https://ieeexplore.ieee.org/document/8126012/
Accession Number : 17397661
Campus : Amritapuri
School : School of Engineering
Department : Computer Science
Year : 2017
Abstract : A transposition tree T can be defined over permutations where the positions within a permutation define the vertices of the tree and an edge (i, j) of T signifies that the symbols at the positions i and j can be swapped. A Cayley graph of a permutation group can be generated by a transposition tree T where the edges of T form the generator set. Identifying the diameter value of a Cayley graph helps is equivalent to determining the maximum possible latency of communication in the corresponding interconnection network where the latency is measured in terms of the number of hops. In general, computation of the diameter is intractable. Thus, determining an upper bound on the diameter value is sought. In particular, tighter upper bounds are keenly pursued. Several existing methods compute an upper bound on the diameter value. The first known method has exponential time complexity. Later on, several articles introduced polynomial time algorithms. This article compares various methods. Furthermore, exact diameters for novel classes of trees are identified.
Cite this Research Publication : S. Uthan and Dr. Bhadrachalam Chitturi, “Bounding the diameter of cayley graphs generated by specific transposition trees”, in 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India, 2017.