Greedy prefix-reversal Gray codes and beyond

Relatore:  Elena Konstantinova - Russian Academy of Sciences and Novosibirsk State University
  martedì 10 maggio 2016 alle ore 14.30 rinfresco 14:15, inizio seminario 14.30
In this talk, generalized Gray codes for the Pancake graph are considered. The Pancake graph is a Cayley graph on the symmetric group S_n generated by prefix-reversals. The notion of the Prefix-reversal Gray code as a class was first introduced in 2013 by A. Williams and J. Sawada, and was suggested as a Hamiltonian cycle algorithm in the Pancake graph. The hamiltonicity of the Pancake graph was known since 1984, when S. Zaks has introduced the algorithm of successive generation of permutations by suffix-reversals, which are obviously isomorphic to prefix-reversals. It is known also that there are all cycles of length  6 <= l <= n!, but there are no cycles of length 3,4 or 5 in the Pancake graph. We present the new concept of Prefix-reversal Gray codes based on independent cycles which extends the known greedy Prefix-reversal Gray code constructions given by Zaks and Williams. Cases of non-existence of codes based on the presented family of independent cycles are provided using the fastening cycle approach. We also give necessary condition for existence of greedy Prefix-reversal Gray codes based on the independent cycles with arbitrary even lengths. Some open questions are discussed.




 

Luogo
Ca' Vignal - Piramide, Piano 0, Sala Verde

Referente
Zsuzsanna Liptak

Referente esterno
Data pubblicazione
15 marzo 2016

Offerta formativa

Condividi