@inproceedings{32dfd862018945d88a37340b04499ec1,
title = "Ranking bracelets in polynomial time",
abstract = "The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k2 · n4), where k is the size of the alphabet and n is the length of the considered bracelets. The key part of the algorithm is to compute the rank of any word with respect to the set of bracelets by finding three other ranks: the rank over all necklaces, the rank over palindromic necklaces, and the rank over enclosing apalindromic necklaces. The last two concepts are introduced in this paper. These ranks are key components to our algorithm in order to decompose the problem into parts. Additionally, this ranking procedure is used to build a polynomial-time unranking algorithm.",
keywords = "Bracelets, Necklaces, Ranking",
author = "Duncan Adamson and Gusev, {Vladimir V.} and Igor Potapov and Argyrios Deligkas",
note = "Publisher Copyright: {\textcopyright} Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas.; 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 ; Conference date: 05-07-2021 Through 07-07-2021",
year = "2021",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.CPM.2021.4",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Pawel Gawrychowski and Tatiana Starikovskaya",
booktitle = "32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021",
}