Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 18, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Dejan Dukaric
For a permutation R of the integers from 1 to n, let f(R) be the smallest number of prefix reversals that will transform R to the identity permutation, and let f(n) be the largest such f(R) for all R in the symmetric group Sn, where a prefix reversal will transform one permutation to another by taking a prefix of the permutation and then reverse this prefix (example: 34251 -> 24351). In my talk I will present proofs for the upper and lower bound of f(n). An application of the pancake problem is the pancake network which looks promising as a network for parallel algorithms.
Source for the proofs: W. Gates and C. Papadimitriou (1979), "Bounds for Sorting by Prefix Reversal"
Sources for further results: D.S. Cohen, M. Blum (1993), "On the Problem of Sorting Burnt Pancakes" M.H. Heydari, I.H. Sudborough (1997), "On the Diameter of the Pancake Network"
Automatic MiSe System Software Version 1.4803M | admin login