Colored Token Swapping Using Broom
L Ajila, T S Indulekha, G Anuja · 2024
Token swapping, a fundamental problem in computational graph theory involves rearranging tokens at graph vertices through minimal swaps to achieve a desired configuration. This problem finds applications in various fields, including task scheduling, DNA rearrangement, and network reconfiguration. A well-established variant, colored token swapping, assigns distinct colors to tokens residing on vertices in a graph. The complexity of token swapping is NP-hard. Two-colored token swapping is a specific case where there are only two distinct colors for the tokens. This work introduces a novel, efficient algorithm for swapping two-colored tokens on a specific tree called a single broom, achieving a configuration where each token resides in its designated position. Single brooms are constructed by attaching the center vertex of a star(the vertex with degree n-2) to one of the leaf nodes of a path. The suggested algorithm utilizes the inherent properties of the tree structure to streamline the necessary swaps for achieving the desired configuration.