Online ISSN:1349-8606
Progress in Informatics  
No.9 March 2012  
Page 3-7  
 
An almost optimal algorithm for Winkler's sorting pairs in bins
Hiro ITO, Junichi TERUYAMA and Yuichi YOSHIDA

LINK [1] M. Bóna and R. Flynn, “Sorting a permutation with block moves,” arXiv:0806.2787v1.

LINK [2] D. Cranston, I. H. Sudborough, and D. B. West, “Short proofs for cut-and-paste sorting of permutations,” Discrete Math., vol.307, pp.2866-2870, 2007.

LINK [3] H. Dweighter, “Elementary Problems,” American Mathematical Monthly, vol.82, p.1010, 1975.

LINK [4] H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wástlund, “Sorting a bridge hand,” Discrete Math., vol.241, pp.289-300, 2001.

LINK [5] S. Elizalde and P. Winkler, “Sorting by Placement and Shift,” Proc. ACM/SIAM Symp. on Discrete Algorithms (SODA), pp.68-75, 2009.

LINK [6] W. H. Gates and C. H. Papadimitriou, “Bounds for sorting by prefix reversal,” Discrete Math., vol.27, pp.47-57, 1979.

LINK [7] M. H. Heydari and I. H. Sudborough, “On the diameter of pancake network,” J. Algorithms, vol.25, pp.67-94, 1997.

LINK [8] H. Ito, J. Teruyama, and Y. Yoshida, “An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins”, IEICE Computation, IEICE Technical Report, vol.109, no.391, COMP2009-45, pp.45-49, 2010.

LINK [9] H. Ito, J. Teruyama, and Y. Yoshida, “An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins”, Proc. of the 3rd Asian Association for Algorithms and Computation (AAAC 2010), p.11, 2010.

LINK [10] D. E. Knuth, Sorting and Searching, volume 3 of The Art of Computer Programming, Addison-Wesley, 1973, Second edition, 1998.

LINK [11] A. Püttmann, “KRAWATTENPROBLEM”, http://www.springer.com/cda/content/document/cda_downloaddocument/SAV_Krawattenraetsel_Loesung_Puettmann

LINK [12] P. Winkler, Mathematical puzzles: A Connoisseur's collection. A K Peters, vol.143, pp.149-151, 2004.

LINK [13] D. B. West: http://www.math.uiuc.edu/~west/regs/sortpair.html, 2008.