Optimal Algorithms for Sorting Permutations with Brooms
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 <inline-formula><math display="inline"><semantics><mrow><mi>T</mi>&...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/7/220 |
| _version_ | 1827619284326547456 |
|---|---|
| author | Indulekha Thekkethuruthel Sadanandan Bhadrachalam Chitturi |
| author_facet | Indulekha Thekkethuruthel Sadanandan Bhadrachalam Chitturi |
| author_sort | Indulekha Thekkethuruthel Sadanandan |
| collection | DOAJ |
| description | 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 <inline-formula><math display="inline"><semantics><mrow><mi>T</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a spanning tree over <i>n</i> vertices <inline-formula><math display="inline"><semantics><mrow><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>…</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>. <i>T</i> denotes an operation in which each edge is a generator. A value assigned to a vertex is called a <i>token</i> or a <i>marker</i>. The markers on vertices <i>u</i> and <i>v</i> can be swapped only if the pair <inline-formula><math display="inline"><semantics><mrow><mo>(</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo>)</mo><mo>∈</mo><mi>E</mi></mrow></semantics></math></inline-formula>. The initial configuration consists of a bijection from the set of vertices <inline-formula><math display="inline"><semantics><mrow><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> to the set of markers <inline-formula><math display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>⋯</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>,</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>. The goal is to <i>sort</i> the initial configuration of <i>T</i>, i.e., an input permutation, by applying the minimum number of swaps or <i>moves</i> in <i>T</i>. 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 <i>broom</i> and its variation a <i>double broom</i>. A <i>single broom</i> is a tree obtained by joining the centre vertex of a star with one of the two leaf vertices of a path graph. A <i>double broom</i> 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 <i>millipede tree</i> and prove that <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>*</mo></msup></semantics></math></inline-formula> yields a tighter upper bound for sorting permutations with a balanced millipede tree compared to <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>′</mo></msup></semantics></math></inline-formula>. Algorithms <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>*</mo></msup></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>′</mo></msup></semantics></math></inline-formula> are designed previously. |
| first_indexed | 2024-03-09T10:23:59Z |
| format | Article |
| id | doaj.art-444432336d374f0ba6f8dcb8376a42fd |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T10:23:59Z |
| publishDate | 2022-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-444432336d374f0ba6f8dcb8376a42fd2023-12-01T21:46:38ZengMDPI AGAlgorithms1999-48932022-06-0115722010.3390/a15070220Optimal Algorithms for Sorting Permutations with BroomsIndulekha Thekkethuruthel Sadanandan0Bhadrachalam Chitturi1Department of Computer Science and Applications, Amrita Vishwa Vidyapeetham, Amritapuri 641112, IndiaDepartment of Computer Science, UT Dallas, Richardson, TX 75080, USASorting permutations with various operations has applications in genetics and computer interconnection networks where an operation is specified by its generator set. A transposition tree <inline-formula><math display="inline"><semantics><mrow><mi>T</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a spanning tree over <i>n</i> vertices <inline-formula><math display="inline"><semantics><mrow><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>…</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>. <i>T</i> denotes an operation in which each edge is a generator. A value assigned to a vertex is called a <i>token</i> or a <i>marker</i>. The markers on vertices <i>u</i> and <i>v</i> can be swapped only if the pair <inline-formula><math display="inline"><semantics><mrow><mo>(</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo>)</mo><mo>∈</mo><mi>E</mi></mrow></semantics></math></inline-formula>. The initial configuration consists of a bijection from the set of vertices <inline-formula><math display="inline"><semantics><mrow><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> to the set of markers <inline-formula><math display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>⋯</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>,</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>. The goal is to <i>sort</i> the initial configuration of <i>T</i>, i.e., an input permutation, by applying the minimum number of swaps or <i>moves</i> in <i>T</i>. 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 <i>broom</i> and its variation a <i>double broom</i>. A <i>single broom</i> is a tree obtained by joining the centre vertex of a star with one of the two leaf vertices of a path graph. A <i>double broom</i> 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 <i>millipede tree</i> and prove that <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>*</mo></msup></semantics></math></inline-formula> yields a tighter upper bound for sorting permutations with a balanced millipede tree compared to <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>′</mo></msup></semantics></math></inline-formula>. Algorithms <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>*</mo></msup></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msup><mi>D</mi><mo>′</mo></msup></semantics></math></inline-formula> are designed previously.https://www.mdpi.com/1999-4893/15/7/220sorting permutationstransposition treespolynomial time algorithmsinterconnection networksbroomoptimal swap sequence |
| spellingShingle | Indulekha Thekkethuruthel Sadanandan Bhadrachalam Chitturi Optimal Algorithms for Sorting Permutations with Brooms Algorithms sorting permutations transposition trees polynomial time algorithms interconnection networks broom optimal swap sequence |
| title | Optimal Algorithms for Sorting Permutations with Brooms |
| title_full | Optimal Algorithms for Sorting Permutations with Brooms |
| title_fullStr | Optimal Algorithms for Sorting Permutations with Brooms |
| title_full_unstemmed | Optimal Algorithms for Sorting Permutations with Brooms |
| title_short | Optimal Algorithms for Sorting Permutations with Brooms |
| title_sort | optimal algorithms for sorting permutations with brooms |
| topic | sorting permutations transposition trees polynomial time algorithms interconnection networks broom optimal swap sequence |
| url | https://www.mdpi.com/1999-4893/15/7/220 |
| work_keys_str_mv | AT indulekhathekkethuruthelsadanandan optimalalgorithmsforsortingpermutationswithbrooms AT bhadrachalamchitturi optimalalgorithmsforsortingpermutationswithbrooms |