2022/04/18 by V R Harigovind, R, Harigovind V, Pramod P Nair +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Genome Rearrangement Algorithms #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2204.08184
The Pancake graph(Pn) represents the group of all permutations on n elements, namely Sn, with respect to the generating set containing all prefix reversals. The diameter of a graph is the maximum of all distances on the graph, where the distance between two vertices is the shortest path between them. In the case of the Pn, it is the maximum of the shortest generating sequence of each permutation in Sn. Here we propose a method to realise better upper bounds to the diameter of Pn that has its focus on Graph Theoretical concepts rather than Algebra.