2018/11/19 by Chitturi, Bhadrachalam, S, Indulekha T
#05C05 #05C12 #05C85 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1811.07443
The set of all permutations with n symbols is a symmetric group denoted by Sn. A transposition tree, T, is a spanning tree over its n vertices VT=1, 2, 3, … n where the vertices are the positions of a permutation π and π is in Sn. T is the operation and the edge set ET denotes the corresponding generator set. The goal is to sort a given permutation π with T. The number of generators of ET that suffices to sort any π∈ Sn constitutes an upper bound. It is an upper bound, on the diameter of the corresponding Cayley graph Γ i.e. diam(Γ). A precise upper bound equals diam(Γ). Such bounds are known only for a few trees. Jerrum showed that computing diam(Γ) is intractable in general if the number of generators is two or more whereas T has n-1 generators. For several operations computing a tight upper bound is of theoretical interest. Such bounds have applications in evolutionary biology to compute the evolutionary relatedness of species and parallel/distributed computing for latency estimation. The earliest algorithm computed an upper bound f(Γ) in a Ω(n!) time by examining all π in Sn. Subsequently, polynomial time algorithms were designed to compute upper bounds or their estimates. We design an upper bound δ^* whose cumulative value for all trees of a given size n is shown to be the tightest for n ≤ 15. We show that δ^* is tightest known upper bound for full binary trees. Keywords: Transposition trees, Cayley graphs, permutations, sorting, upper bound, diameter, greedy algorithms.