Algorithms for Gray codes and combinatorial generation
| Thesis title in Czech: | Algoritmy pro Grayovy kódy a kombinatorické generování |
|---|---|
| Thesis title in English: | Algorithms for Gray codes and combinatorial generation |
| Key words: | cache-oblivious algoritmy, datové struktury, paměťová hierarchie, I/O model |
| English key words: | cache-oblivious algorithms, data structures, memory hierarchy, I/O model |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | dissertation |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | RNDr. Jiří Fink, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 30.09.2019 |
| Date of assignment: | 30.09.2019 |
| Confirmed by Study dept. on: | 04.10.2019 |
| Advisors: | Torsten Mütze, Ph.D. |
| Guidelines |
| A fundamental ingredient of computer science is the study of various classes of combinatorial objects. These may include bitstrings of fixed length, permutations of some ground set, binary trees with a certain number of nodes or spanning trees of a fixed graph. A combinatorial Gray code is a listing of all combinatorial objects in a given class such that any two consecutive objects differ in a (prescribed) small way. This is equivalent to a Hamiltonian path in the corresponding flip graph of the class, which has as vertices the combinatorial objects and edges between pairs of objects that differ in the specified way. Gray codes are closely tied to combinatorial generation, since low delay between consecutively generated objects means that the objects cannot differ "too much". One of the basic questions is whether a Gray code for some class of objects exists, and if so, how to generate it efficiently by an algorithm. Apart from that, Gray codes have many other applications and are related to fields like graph theory, order theory, and algebra.
The goal of this thesis is to study algorithms for combinatorial generation problems and specifically for Gray codes, as well as related topics. This may include design and implementation of new algorithms, improvement of existing algorithms, as well as design of new Gray codes or applications of existing results to other fields. Some of the open problems that could be studied within the thesis are: * Simplified algorithms for the middle levels problem: The middle levels problem asks whether there is a Gray code for all bitstrings of length 2k+1 and Hamming weight k or k+1, so that any two consecutive bitstrings differ in exactly one position. The problem has a positive answer and there is even a loopless algorithm for this Gray code. However, the algorithm is quite complicated and it would be desirable to design a simpler algorithm. * Algorithms for the central levels problem: The central levels problem is a generalization of the middle levels problem, where we consider all bitstrings of length 2k+1 whose Hamming weight is in some interval [k-c, k+1+c], for some fixed c. Although such a Gray code is known to exist, there is no efficient algorithm yet. * Applications of the Hartung-Hoang-Mütze-Williams framework: Hartung et al. (SODA 2020) presented a versatile and general algorithmic framework for exhaustive generation of various combinatorial objects. The authors have applied their framework to provide a unified view on several previously known results and to obtain new Gray codes along with efficient algorithms. The framework has a great potential to yield many more new results, for example in problems concerning acyclic orientations of graphs and acyclic reorientation lattices. |
| References |
| MÜTZE, Torsten. Combinatorial Gray codes-an updated survey. arXiv preprint arXiv:2202.01280, 2022.
KNUTH, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 2014. KNUTH, Donald E. The Art of Computer Programming. Vol. 4–Pre-fascicle 8A. Hamiltonian paths and cycles. 2020. Available at https://www-cs-faculty.stanford.edu/~knuth/fasc8a.ps.gz. MÜTZE, Torsten; NUMMENPALO, Jerri. A Constant-Time Algorithm for Middle Levels Gray Codes. Algorithmica, 2020, 82.5: 1239-1258. ARNDT, Jörg. Matters Computational: ideas, algorithms, source code. Springer Science & Business Media, 2010. HARTUNG, Elizabeth, et al. Combinatorial generation via permutation languages. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020. p. 1214-1225. |