Computing the diameters of 14- and 15-pancake graphs

摘要

Computing the diameter of a pancake graph is equivalent to solving the "pancake sorting problem" (or "prefix reversal problem"), which is basically the problem of finding the maximum number of pancake flips one would need to perform in order to sort an arbitrary stack of pancakes. The diameter of a pancake graph can be computed by solving the shortest path problems from a certain vertex to every other vertex in the graph. However, finding the diameter of an n-pancake graph is known to be a very hard problem. In fact, n=13 is the maximum size of n-pancake graphs whose diameters have been computed. Heydari et al. developed a method for calculating the diameter of the 13-pancake graph. In this paper, an extension of that method is proposed and used to obtain the diameters of the 14- and 15-pancake graphs.