The Library
Combinatorial Gray codes : an updated survey
Tools
Mutze, Torsten (2023) Combinatorial Gray codes : an updated survey. Electronic Journal of Combinatorics, 30 (3). DS:26. doi:10.37236/11023 ISSN 1077-8926.
|
PDF
11023-PDF file-45589-3-10-20230710.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons: Attribution-No Derivative Works 4.0. Download (3018Kb) | Preview |
|
PDF
survey.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (3305Kb) |
Official URL: https://doi.org/10.37236/11023
Abstract
A combinatorial Gray code for a class of objects is a listing that contains each object from the class exactly once such that any two consecutive objects in the list differ only by a `small change'. Such listings are known for many different combinatorial objects, including bitstrings, combinations, permutations, partitions, triangulations, but also for objects defined with respect to a fixed graph, such as spanning trees, perfect matchings or vertex colorings. This survey provides a comprehensive picture of the state-of-the-art of the research on combinatorial Gray codes. In particular, it gives an update on Savage's influential survey [C. D. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997.], incorporating many more recent developments. We also elaborate on the connections to closely related problems in graph theory, algebra, order theory, geometry and algorithms, which embeds this research area into a broader context. Lastly, we collect and propose a number of challenging research problems, thus stimulating new research endeavors.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
Library of Congress Subject Headings (LCSH): | Gray codes, Combinatorial analysis | ||||||
Journal or Publication Title: | Electronic Journal of Combinatorics | ||||||
Publisher: | Electronic Journal of Combinatorics | ||||||
ISSN: | 1077-8926 | ||||||
Official Date: | 14 July 2023 | ||||||
Dates: |
|
||||||
Volume: | 30 | ||||||
Number: | 3 | ||||||
Article Number: | DS:26 | ||||||
DOI: | 10.37236/11023 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Description: | Dynamic Surveys https://www.combinatorics.org/ojs/index.php/eljc/issue/view/Surveys |
||||||
Date of first compliant deposit: | 19 January 2024 | ||||||
Date of first compliant Open Access: | 19 January 2024 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year