Publications

Authors:

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

Title:

Constant Time and Space Updates for the Sigma-Tau Problem

Year:

2023

Type of item:

Contributo in atti di convegno

Tipologia ANVUR:

Contributo in Atti di convegno

Language:

Inglese

Format:

A Stampa

Name of journal:

LECTURE NOTES IN COMPUTER SCIENCE

ISSN of journal:

0302-9743

N° Volume:

14240

Congresso:

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

Place:

Pisa, Italy

Period:

Sept. 26-28, 2023

:

Springer Verlag Germany

Publisher:

Springer Verlag Germany

ISBN:

978-3-031-43979-7

Page numbers:

323-330

Keyword:

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

Short description of contents:

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.

Product ID:

137161

Handle IRIS:

11562/1105806

Last Modified:

June 20, 2024

Bibliographic citation:

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 , Proceedings of "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