Pubblicazioni

Autori:

Liptak, Zsuzsanna; Masillo, Francesco; Navarro, Gonzalo; Williams, Aaron

Titolo:

Constant Time and Space Updates for the Sigma-Tau Problem

Anno:

2023

Tipologia prodotto:

Contributo in atti di convegno

Tipologia ANVUR:

Contributo in Atti di convegno

Lingua:

Inglese

Formato:

A Stampa

Nome rivista:

LECTURE NOTES IN COMPUTER SCIENCE

ISSN Rivista:

0302-9743

N° Volume:

14240

Titolo del Convegno:

30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)

Luogo:

Pisa, Italy

Periodo:

Sept. 26-28, 2023

Editore:

Springer Verlag Germany

Casa editrice:

Springer Verlag Germany

ISBN:

978-3-031-43979-7

Intervallo pagine:

323-330

Parole chiave:

permutations, sigma-tau problem, dynamic data structures, combinatorial generation, combinatorial Gray codes

Breve descrizione dei contenuti:

Sawada and Williams in [SODA 2018] and [ACM Trans. Alg. 2020] gave algorithms for constructing Hamiltonian paths and cycles in the Sigma-Tau graph, thereby solving a problem of Nijenhuis and Wilf that had been open for over 40 years. The Sigma-Tau graph is the di- rected graph whose vertex set consists of all permutations of n, and there is a directed edge from π to π′ if π′ can be obtained from π either by a cyclic left-shift (sigma) or by exchanging the first two entries (tau). We improve the existing algorithms from O(n) time per permutation to O(1) time per permutation. Moreover, our algorithms require only O(1) extra space. The result is the first combinatorial generation algorithm for n-permutations that is optimal in both time and space, and which lists the objects in a Gray code order using only two types of changes.

Id prodotto:

137161

Handle IRIS:

11562/1105806

ultima modifica:

20 giugno 2024

Citazione bibliografica:

Liptak, Zsuzsanna; Masillo, Francesco; Navarro, Gonzalo; Williams, Aaron, Constant Time and Space Updates for the Sigma-Tau Problem in «LECTURE NOTES IN COMPUTER SCIENCE» vol. 14240 Springer Verlag Germany  in Proc. of the 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023) , Springer Verlag Germany , Atti di "30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)" , Pisa, Italy , Sept. 26-28, 2023 , 2023 , pp. 323-330

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo