Name
Abstract | ||
|---|---|---|
Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances). Let each sequence have the same number k of 1's. We are interested in computing the cyclic swap distance between A and B, i.e., the minimum number of swaps needed to convert A into B, minimized over all rotations of B. We show that this distance may be approximated in O(n + k2) time. |
Year | Venue | Field |
|---|---|---|
2005 | Stringology | Discrete mathematics,Approximation algorithm,Combinatorics,Karloff–Zwick algorithm,Necklace,Out-of-kilter algorithm,Minimax approximation algorithm,Christofides algorithm,Mathematics,Polynomial-time approximation scheme,Cornacchia's algorithm |
DocType | Citations | PageRank |
Conference | 3 | 0.38 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoan José Pinzón Ardila | 1 | 7 | 1.86 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Gad M. Landau | 3 | 1558 | 239.71 |
| Manal Mohamed | 4 | 102 | 12.62 |