{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T05:49:41Z","timestamp":1775022581747,"version":"3.50.1"},"reference-count":10,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> Permutations are discrete structures that naturally model a genome where every gene occurs exactly once. In a permutation over the given alphabet [Formula: see text], each symbol of [Formula: see text] appears exactly once. A transposition operation on a given permutation [Formula: see text] exchanges two adjacent sublists of [Formula: see text]. If one of these sublists is restricted to be a prefix then one obtains a prefix transposition. The symmetric group of permutations with [Formula: see text] symbols derived from the alphabet [Formula: see text] is denoted by [Formula: see text]. The symmetric prefix transposition distance between [Formula: see text] and [Formula: see text] is the minimum number of prefix transpositions that are needed to transform [Formula: see text] into [Formula: see text]. It is known that transforming an arbitrary [Formula: see text] into an arbitrary [Formula: see text] is equivalent to sorting some [Formula: see text]. Thus, upper bound for transforming any [Formula: see text] into any [Formula: see text] with prefix transpositions is simply the upper bound to sort any permutation [Formula: see text]. The current upper bound is [Formula: see text] for prefix transposition distance over [Formula: see text]. In this paper, we improve the same to [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s1793830920500779","type":"journal-article","created":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T06:33:05Z","timestamp":1591943585000},"page":"2050077","source":"Crossref","is-referenced-by-count":5,"title":["A new upper bound for sorting permutations with prefix transpositions"],"prefix":"10.1142","volume":"12","author":[{"given":"Pramod P.","family":"Nair","sequence":"first","affiliation":[{"name":"Department of Mathematics, Amrita Vishwa Vidyapeetham, Amritapuri, India"}]},{"given":"Rajan","family":"Sundaravaradhan","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Amrita Vishwa Vidyapeetham, Amritapuri, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8768-9183","authenticated-orcid":false,"given":"Bhadrachalam","family":"Chitturi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA"}]}],"member":"219","published-online":{"date-parts":[[2020,9,11]]},"reference":[{"issue":"4","key":"S1793830920500779BIB001","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","volume":"38","author":"Akers S. B.","year":"1989","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"S1793830920500779BIB002","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"Bafna V.","year":"1998","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"S1793830920500779BIB003","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/110851390","volume":"26","author":"Bulteau L.","year":"2012","journal-title":"SIAM J. Discrete Math."},{"key":"S1793830920500779BIB005","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2015.07.059","volume":"602","author":"Chitturi B.","year":"2015","journal-title":"Theoret. Comput. Sci."},{"key":"S1793830920500779BIB006","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1109\/HICSS.2008.75","volume-title":"Proc. 41st Annual Hawaii Int. Conf. System Sciences (HICSS 2008)","author":"Chitturi B.","year":"2008"},{"key":"S1793830920500779BIB007","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.tcs.2011.11.018","volume":"421","author":"Chitturi B.","year":"2012","journal-title":"Theoret. Comput. Sci."},{"key":"S1793830920500779BIB009","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-45735-6_7","volume":"2476","author":"Dias Z.","year":"2002","journal-title":"Lecture Notes Comput. Sci."},{"key":"S1793830920500779BIB010","series-title":"Advances in Experimental Medicine and Biology","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1007\/978-1-4419-5913-3_81","volume-title":"Advances in Computational Biology","volume":"680","author":"Feng X.","year":"2010"},{"issue":"1","key":"S1793830920500779BIB012","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0166-218X(98)00072-9","volume":"88","author":"Heath L. S.","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"S1793830920500779BIB013","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0167-8191(93)90054-O","volume":"19","author":"Lakshmivarahan S.","year":"1993","journal-title":"Parallel Comput."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830920500779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,29]],"date-time":"2020-11-29T05:01:16Z","timestamp":1606626076000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830920500779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,11]]},"references-count":10,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S1793830920500779"],"URL":"https:\/\/doi.org\/10.1142\/s1793830920500779","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,11]]}}}