{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T04:14:16Z","timestamp":1762056856601,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,6,21]],"date-time":"2022-06-21T00:00:00Z","timestamp":1655769600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Sorting permutations with various operations has applications in genetics and computer interconnection networks where an operation is specified by its generator set. A transposition tree T=(V,E) is a spanning tree over n vertices v1,v2,\u2026vn. T denotes an operation in which each edge is a generator. A value assigned to a vertex is called a token or a marker. The markers on vertices u and v can be swapped only if the pair (u,v)\u2208E. The initial configuration consists of a bijection from the set of vertices v1,v2,\u2026,vn to the set of markers (1,2,\u22ef,n\u22121,n). The goal is to sort the initial configuration of T, i.e., an input permutation, by applying the minimum number of swaps or moves in T. Computationally tractable optimal algorithms to sort permutations are known only for a few classes of transposition trees. We study a class of transposition trees called a broom and its variation a double broom. A single broom is a tree obtained by joining the centre vertex of a star with one of the two leaf vertices of a path graph. A double broom is an extension of a single broom where the centre vertex of a second star is connected to the terminal vertex of the path in a single broom. We propose a simple and efficient algorithm to obtain an optimal swap sequence to sort permutations with the transposition tree broom and a novel optimal algorithm to sort permutations with a double broom. We also introduce a new class of trees named millipede tree and prove that D* yields a tighter upper bound for sorting permutations with a balanced millipede tree compared to D\u2032. Algorithms D* and D\u2032 are designed previously.<\/jats:p>","DOI":"10.3390\/a15070220","type":"journal-article","created":{"date-parts":[[2022,6,21]],"date-time":"2022-06-21T21:55:19Z","timestamp":1655848519000},"page":"220","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimal Algorithms for Sorting Permutations with Brooms"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3188-6097","authenticated-orcid":false,"given":"Indulekha","family":"Sadanandan","sequence":"first","affiliation":[{"name":"Department of Computer Science and Applications, Amrita Vishwa Vidyapeetham, Amritapuri 641112, India"}]},{"given":"Bhadrachalam","family":"Chitturi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, UT Dallas, Richardson, TX 75080, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","article-title":"A group-theoretic model for symmetric interconnection networks","volume":"38","author":"Akers","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"ref_2","unstructured":"Chitturi, B. (2017, June 01). On Transforming Sequences. Available online: https:\/\/www.researchgate.net\/profile\/Bhadrachalam-Chitturi\/publication\/308524758_ON_TRANSFORMING_SEQUENCES\/links\/57e64be408aed7fe4667bb11\/ON-TRANSFORMING-SEQUENCES.pdf."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Heydemann, M.-C. (1997). Cayley graphs and interconnection networks. Graph Symmetry, Springer.","DOI":"10.1007\/978-94-015-8937-6_5"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0167-8191(93)90054-O","article-title":"Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey","volume":"19","author":"Lakshmivarahan","year":"1993","journal-title":"Parallel Comput."},{"key":"ref_5","unstructured":"Jain, B.A., Lubiw, K., Mas\u00e1rov\u00e1, A., Miltzow, Z., Mondal, T., Naredl, D., Murty, A., Josef, T., and Alexi, T. (2019). Token Swapping on Trees. arXiv."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.tcs.2015.01.052","article-title":"Swapping labeled tokens on graphs","volume":"586","author":"Yamanaka","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0166-218X(92)90127-V","article-title":"New methods for using Cayley graphs in interconnection networks","volume":"37\u201338","author":"Cooperman","year":"1992","journal-title":"Discret. Appl. Math."},{"key":"ref_8","unstructured":"Xu, J. (2013). Topological Structure and Analysis of Interconnection Networks, Springer Science & Business Media."},{"key":"ref_9","unstructured":"Knuth, D.E. (1997). The Art of Computer Programming: Sorting and Searching, Pearson Education. [2nd ed.]."},{"key":"ref_10","first-page":"129","article-title":"Factoring a permutation on a broom","volume":"30","author":"Vaughan","year":"1999","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kawahara, J., Saitoh, T., and Yoshinaka, R. (2017). The Time Complexity of the Token Swapping Problem and Its Parallel Variants. Walcom Algorithms Comput., 448\u2013459.","DOI":"10.1007\/978-3-319-53925-6_35"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","article-title":"The complexity of finding minimum-length generator sequences","volume":"36","author":"Jerrum","year":"1985","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","unstructured":"Christie, D.A. (1998). Genome Rearrangement Problems, The University of Glasgow."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.tcs.2018.09.015","article-title":"Sorting permutations with transpositions in O(n3) amortized time","volume":"766","author":"Chitturi","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_15","first-page":"183","article-title":"Computing cardinalities of subsets of Sn with k adjacencies","volume":"113","author":"Chitturi","year":"2020","journal-title":"JCMCC"},{"key":"ref_16","unstructured":"Malavika, J., Scaria, S., and Indulekha, T.S. (2021, January 2\u20134). On Token Swapping in Labeled Tree. Proceedings of the 2021 Third International Conference on Inventive Research in Computing Applications (ICIRCA), Coimbatore, India."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2656","DOI":"10.1007\/s00453-017-0387-0","article-title":"Complexity of Token Swapping and Its Variants","volume":"80","author":"Bonnet","year":"2017","journal-title":"Algorithmica"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.7155\/jgaa.00483","article-title":"The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant","volume":"23","author":"Kawahara","year":"2019","journal-title":"JGAA"},{"key":"ref_19","unstructured":"Miltzow, T., Narins, L., Okamoto, Y., Rote, G., Thomas, A., and Uno, T. (2016, January 22\u201324). Approximation and hardness of token swapping. Proceedings of the 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1080\/14786444908646287","article-title":"LXXVII. Note on the theory of permutations","volume":"34","author":"Cayley","year":"1849","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/S0012-365X(98)00377-X","article-title":"Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ARY trees","volume":"204","author":"Pak","year":"1999","journal-title":"Discrete Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0195-6698(13)80127-8","article-title":"Whitney Numbers of the Second Kind for the Star Poset","volume":"11","author":"Portier","year":"1990","journal-title":"Eur. J. Comb."},{"key":"ref_23","first-page":"214","article-title":"An efficient algorithm for the diameter of cayley graphs generated by transposition trees","volume":"42","author":"Ganesan","year":"2012","journal-title":"Aeng Int. J. Appl. Math."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1350003","DOI":"10.1142\/S1793830913500031","article-title":"Upper Bounds For Sorting Permutations With A Transposition Tree","volume":"5","author":"Chitturi","year":"2013","journal-title":"Discret. Math. Algorithm. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.dam.2014.10.019","article-title":"Diameters of Cayley graphs generated by transposition trees","volume":"184","author":"Kraft","year":"2015","journal-title":"Discret. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Uthan, S., and Chitturi, B. (2017, January 13\u201316). Bounding the diameter of Cayley graphs generated by specific transposition trees. Proceedings of the International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India.","DOI":"10.1109\/ICACCI.2017.8126012"},{"key":"ref_27","first-page":"369","article-title":"On inversions and cycles in permutations","volume":"36","author":"Balcza","year":"1992","journal-title":"Period. Polytech. Civ. Eng."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/S0195-6698(87)80031-8","article-title":"On Inversions and Cycles in Permutations","volume":"8","author":"Edelman","year":"1987","journal-title":"Eur. J. Comb."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Chitturi, B., and Indulekha, T.S. (2019, January 15\u201317). Sorting permutations with a transposition tree. Proceedings of the 8th International Conference on Modeling Simulation and Applied Optimization (ICMSAO), Manama, Bahrain.","DOI":"10.1109\/ICMSAO.2019.8880398"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.procs.2020.04.008","article-title":"An Upper Bound For Sorting Permutations With A Transposition Tree","volume":"171","author":"Das","year":"2020","journal-title":"Procedia Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Indulekha, T.S., and Chitturi, B. (2019, January 25\u201328). Analysis of Algorithm \u03b4* on full binary trees. Proceedings of the 2019 Second International Conference on Advanced Computational and Communication Paradigms (ICACCP), Gangtok, India.","DOI":"10.1109\/ICACCP.2019.8882918"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/220\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:36:28Z","timestamp":1760139388000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,21]]},"references-count":31,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["a15070220"],"URL":"https:\/\/doi.org\/10.3390\/a15070220","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,6,21]]}}}