--- res: bibo_abstract: - "The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results:\r\n1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.\r\n3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices \ have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Ahmad foaf_name: Biniaz, Ahmad foaf_surname: Biniaz - foaf_Person: foaf_givenName: Kshitij foaf_name: Jain, Kshitij foaf_surname: Jain - foaf_Person: foaf_givenName: Anna foaf_name: Lubiw, Anna foaf_surname: Lubiw - foaf_Person: foaf_givenName: Zuzana foaf_name: Masárová, Zuzana foaf_surname: Masárová foaf_workInfoHomepage: http://www.librecat.org/personId=45CFE238-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-6660-1322 - foaf_Person: foaf_givenName: Tillmann foaf_name: Miltzow, Tillmann foaf_surname: Miltzow - foaf_Person: foaf_givenName: Debajyoti foaf_name: Mondal, Debajyoti foaf_surname: Mondal - foaf_Person: foaf_givenName: Anurag Murty foaf_name: Naredla, Anurag Murty foaf_surname: Naredla - foaf_Person: foaf_givenName: Josef foaf_name: Tkadlec, Josef foaf_surname: Tkadlec foaf_workInfoHomepage: http://www.librecat.org/personId=3F24CCC8-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-1097-9684 - foaf_Person: foaf_givenName: Alexi foaf_name: Turcotte, Alexi foaf_surname: Turcotte dct_date: 2019^xs_gYear dct_language: eng dct_title: Token swapping on trees@ ...