Ranking Bracelets in Polynomial Time



Adamson, Duncan, Deligkas, Argyrios, Gusev, Vladimir V and Potapov, Igor
(2021) Ranking Bracelets in Polynomial Time. In: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021).

[img] Text
2104.04324v1.pdf - Submitted version

Download (659kB) | Preview

Abstract

The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k^2 n^4), 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.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: math.CO, math.CO, cs.DM, cs.DS
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 13 Apr 2021 09:47
Last Modified: 18 Jan 2023 22:53
DOI: 10.4230/LIPIcs.CPM.2021.4
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3119146