No Access

UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE

Department of Computer Science, Amrita Vishwa Vidyapeetham University, Amritapuri Campus, Clappana P.O., Kollam 690525, Kerala, India

Search for more papers by this author

https://doi.org/10.1142/S1793830913500031Cited by:13 (Source: Crossref)

Abstract

An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n²) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n²) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n²) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ).

Keywords:

AMSC: 05C30, 11Y16, 68Q25, 68R05, 68R10

References

S. B. Akers and B. Krishnamurthy, IEEE Trans. Comput. 38(4), 555 (1989), DOI: 10.1109/12.21148. Crossref, Google Scholar
S. C. Bruell, SIAM J. Comput. 29(2), 600 (1999), DOI: 10.1137/S0097539798427156. Crossref, Google Scholar
L. Bulteau, G. Fertin and I. Rusu, Lect. Notes Comput. Sci. 7464, 247 (2012), DOI: 10.1007/978-3-642-32589-2_24. Crossref, Google Scholar
B. Chitturi, On transforming sequences, Ph.D. Thesis, Department of Computer Science, University of Texas at Dallas (2007) . Google Scholar
B. Chitturi, Discrete Math. Algorithms Appl. 3(3), 269 (2011), DOI: 10.1142/S1793830911001206. Link, Google Scholar
B. Chitturiet al., Theor. Comput. Sci. 410(36), 3372 (2009), DOI: 10.1016/j.tcs.2008.04.045. Crossref, Google Scholar
B. Chitturi and I. H. Sudborough, Theor. Comput. Sci. 421, 15 (2012), DOI: 10.1016/j.tcs.2011.11.018. Crossref, Google Scholar
B. Chitturiet al., Adjacent Swaps on Strings, Lecture Notes in Computer Science 5092 (Springer-Verlag, 2008) pp. 299–308. Crossref, Google Scholar
T. H. Cormen , C. E. Leiserson and R. L. Rivest , Introduction to Algorithms , 2nd edn. ( The MIT Press , 2001 ) . Google Scholar
G. Cormode, Sequence distance embeddings, Ph.D. thesis, University of Warwick (2003) . Google Scholar
D. Z. Du and F. Hsu , Combinatorial Network Theory , Applied Optimization Series ( Springer , 1995 ) . Google Scholar
X. Feng , B. Chitturi and H. Sudborough , Advances in Computational Biology , Advances in Experimental Medicine and Biology 680 ( Springer-Verlag , 2010 ) . Google Scholar
G. Fertin et al. , Combinatorics of Genome Rearrangements ( The MIT Press , 2009 ) . Crossref, Google Scholar
A. Ganesan, Commun. Comput. Inform. Sci. 283, 54 (2012), DOI: 10.1007/978-3-642-28926-2_6. Crossref, Google Scholar
A. Ganesan, International Journal of Applied Mathematics 42(4), 214 (2012), http://arXiv.org/abs/1202.5888. Google Scholar
W. H. Gates and C. H. Papadimitriou, Discrete Math. 27(1), 47 (1979), DOI: 10.1016/0012-365X(79)90068-2. Crossref, Google Scholar
M. C. Heydemann, Graph Symmetry: Algebraic Methods and Applications (Kluwer Academic Publishers, Dordrecht, 1997) pp. 167–226. Crossref, Google Scholar
M. C. Heydemann, N. Marlin and S. Prennes, Eur. J. Comb. 22(2), 179 (2001), DOI: 10.1006/eujc.2000.0460. Crossref, Google Scholar
http://www.codechef.com/ . Google Scholar
http://www.notesandreviews.com/ . Google Scholar
http://www.sagemath.org/ . Google Scholar
C. Hurkenset al., SIAM J. Discrete Math. 21(3), 592 (2007), DOI: 10.1137/060664252. Crossref, Google Scholar
M. Jerrum, Theor. Comput. Sci. 36, 265 (1985), DOI: 10.1016/0304-3975(85)90047-7. Crossref, Google Scholar
D. E. Knuth , The Art of Computer Programming , Sorting and Searching 3 ( Addison-Wesley Publishing Company , 1973 ) . Google Scholar
S. Lakshmivarahan, J.-S. Jho and S. K. Dhall, Parallel Comput. 19, 361 (1993), DOI: 10.1016/0167-8191(93)90054-O. Crossref, Google Scholar
L. Morales and H. Sudborough, The Essence of Computation, Lecture Notes in Computer Science 2566 (Springer, 2002) pp. 18–36. Crossref, Google Scholar
A. B. Murdasov, Cybernet. Systems Anal. 12(1), 157 (1976). Crossref, Google Scholar
A. J. Radcliffe, A. D. Scott and E. L. Wilmer, SIAM J. Discrete Math. 19(1), 224 (2005), DOI: 10.1137/S0895480103433550. Crossref, Google Scholar
J. H. Smith, J. Combin. Theory 85, 92 (1999), DOI: 10.1006/jcta.1998.2905. Crossref, Google Scholar
J. Xu , Topological Structure and Analysis of Interconnection Networks ( Kluwer Academic Publishers , 2001 ) . Crossref, Google Scholar