---
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
- foaf_Person:
foaf_givenName: Alexi
foaf_name: Turcotte, Alexi
foaf_surname: Turcotte
dct_date: 2019^xs_gYear
dct_language: eng
dct_publisher: ArXiv@
dct_title: Token swapping on trees@
...