Sorting Permutations on an n − Broom

Ranjith Rajesh, Rajan Sundaravaradhan and Bhadrachalam Chitturi ()
Additional contact information
Ranjith Rajesh: Department of Mathematics, Amrita Vishwa Vidyapeetham, Amaravati 522503, Andhra Pradesh, India
Rajan Sundaravaradhan: Department of Mathematics, Amrita Vishwa Vidyapeetham, Amritapuri 690525, Kerala, India
Bhadrachalam Chitturi: Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA

Mathematics, 2024, vol. 12, issue 17, 1-15

Abstract: With applications in computer networks, robotics, genetics, data center network optimization, cryptocurrency exchange, transportation and logistics, cloud computing, and social network analysis, the problem of sorting permutations on transposition trees under various operations is highly relevant. The goal of the problem is to sort or rearrange the markers in a predetermined order by swapping them out at the vertices of a tree in the fewest possible swaps. Only certain classes of transposition trees, like path, star, and broom, have computationally efficient algorithms for sorting permutations. In this paper, we examine the so-called n − b r o o m transposition trees. A single broom or simply a b r o o m is a spanning tree formed by joining the center of the star graph with one end of the path graph. A generalized version of a broom known as an n − b r o o m is created by joining the ends of n brooms to one vertex, known as the n − b r o o m center. By using the idea of clear path markers, we present a novel algorithm for sorting permutations on an n − b r o o m for n > 2 that reduces to a novel 2 − b r o o m algorithm and that further reduces to two instances of a 1 − b r o o m algorithm. Our single-broom algorithm is similar to that of Kawahara et al.; however, our proof of optimality for the same is simpler.

Keywords: sorting permutations; transposition tree; broom; n ? broom; clear path marker; optimal swap sequence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/17/2620/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/17/2620/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:17:p:2620-:d:1463150

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().