Perfect Snake-in-the-Box Codes for Rank Modulation

DOI10.1109/TIT.2016.2620160MaRDI QIDQ2979080zbMATH OpenOpenAlexFDO

Authors A. E. Holroyd

Publication date 2 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08073

Mathematics Subject Classification ID

Combinatorial codes (94B25) Modulation and demodulation in information and communication theory (94A14)

Abstract: For odd n, the alternating group on n elements is generated by the permutations that jump an element from any odd position to position 1. We prove Hamiltonicity of the associated directed Cayley graph for all odd n not equal to 5. (A result of Rankin implies that the graph is not Hamiltonian for n=5.) This solves a problem arising in rank modulation schemes for flash memory. Our result disproves a conjecture of Horovitz and Etzion, and proves another conjecture of Yehezkeally and Schwartz.

Cited in

(11)

• scientific article; zbMATH DE number 2154157 (Why is no real title available?)
• On a combinatorial generation problem of Knuth
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Isomorphism of maximum length circuit codes
• Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
• Snake-in-the-Box Codes for Rank Modulation
• Kneser graphs are Hamiltonian
• Gray codes and symmetric chains
• Gray codes and symmetric chains
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• Sparse Kneser graphs are Hamiltonian

This page was built for publication: Perfect Snake-in-the-Box Codes for Rank Modulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979080)