A 2.25-Approzimation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
We consider sorting unsigned circular permutations by cut-and-paste operations. For a circular permutation, a cut-and-paste operation can be a reversal, a transposition, or a transreversal. For the sorting of signed permutations, there are several approximation algorithms allowing various combinations of these operations. For the sorting of unsigned permutations, we only know a 3-approximation algorithm and an improved algorithm with ratio 2.8386+6, both allowing reversals and transpositions. In this paper, by new observations on the breakpoint graph, we present a 2.25-approximation algorithm for cut-and-paste sorting of unsigned circular permutations.
Xiaowen Lou Darning Zhu
School of Computer Science and Technology, Shandong University,Jinan 250101, P.R. China School of Computer Science and Technology, Shandong University, Jinan 250101, P.R. China
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
331-341
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）