Artificial Intelligence techniques for searching paths and cycles in hypercubes

• Thesis title in Czech: Techniky umělé inteligence pro hledání cest a kružnic v hyperkrychli
• Thesis title in English: Artificial Intelligence techniques for searching paths and cycles in hypercubes
• Academic year of topic announcement: 2023/2024
• Thesis type: diploma thesis
• 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: 26.11.2023
• Date of assignment: 27.11.2023
• Confirmed by Study dept. on: 27.11.2023
• Opponents: Torsten Mütze, Ph.D.

Guidelines

The goal of the thesis is to study paths and cycles in the hypercubes with additional properties presented in [1].
The student will use alpha-beta pruning to reduce the number of cases needed to verify a variant of Ruskey-Savage conjecture in small dimensions.
Then, student will compare different methods to find a path in the hypercube with special properties (e.g. order-preserving paths) based on backtracking, SAT/CSP, genetic programming or machine learning.

References

[1] Mütze, Torsten. "Combinatorial Gray codes-an updated survey." arXiv preprint arXiv:2202.01280 (2022).
[2] Zulkoski, Edward, Vijay Ganesh, and Krzysztof Czarnecki. "MathCheck: A math assistant via a combination of computer algebra systems and SAT solvers." Automated Deduction-CADE-25: 25th International Conference on Automated Deduction, Berlin, Germany, August 1-7, 2015, Proceedings 25. Springer International Publishing, 2015.
[3] Fink, Jiří. "Perfect matchings extend to Hamilton cycles in hypercubes." Journal of Combinatorial Theory, Series B 97.6 (2007): 1074-1076.