Synchronizace automatů
| Thesis title in thesis language (Slovak): | Synchronizace automatů |
|---|---|
| Thesis title in Czech: | Synchronizace automatů |
| Thesis title in English: | Synchronizing automata |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | slovenština |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Štěpán Holub, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 03.10.2012 |
| Date of assignment: | 31.10.2012 |
| Confirmed by Study dept. on: | 23.11.2012 |
| Date and time of defence: | 12.09.2013 00:00 |
| Date of electronic submission: | 01.08.2013 |
| Date of submission of printed version: | 02.08.2013 |
| Date of proceeded defence: | 12.09.2013 |
| Opponents: | RNDr. Michal Hojsík, Ph.D. |
| Guidelines |
| Student popíše Trahtmanovo řešení problému barvení grafu a související barvící algoritmus. Zpracuje také známé informace o složitosti tohoto algoritmu. |
| References |
| A.N. Trahtman,"An Algorithm for Road Coloring." J. of Discrete Algorithms, 16 (2012), Springer, 213--223
A.N. Trahtman, "Synchronizing road coloring", in: 5th IFIP WCC–TCS, 2008, in: SSCS, vol. 273, Springer, 2008, pp. 43–53. A.N. Trahtman, "The road coloring problem", Israel J. Math. 172 (1) (2009) 51–60. M.P. Béal, D. Perrin, "A quadratic algorithm for road coloring", arXiv:0803.0726v2 [cs.DM], 2008. |