Srovnání implementací DecreaseKey hald
| Thesis title in Czech: | Srovnání implementací DecreaseKey hald |
|---|---|
| Thesis title in English: | Comparison of implementations of DecreaseKey Heaps |
| Key words: | Halda|Amortizovaná složitost|Složitost v nejhorším případě |
| English key words: | Heap|Arortized complexity|Worst case complexity |
| Academic year of topic announcement: | 2025/2026 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | Mgr. Vladan Majerech, Dr. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 05.07.2025 |
| Date of assignment: | 08.07.2025 |
| Confirmed by Study dept. on: | 08.07.2025 |
| Guidelines |
| Student implementuje několik variant DecreaseKey hald, přinejmenším Fibonacciho haldy a Haldy s globálně omezenými ztrátami a zásobníky nedokončených redukcí.
Cílem je srovnat efektivitu uvedených hald. Jako testovací případ je vybrán Fredman-Tarjan algoritmus na hledání minimální kostry v náhodných grafech. |
| References |
| [1] Fibonacci heaps and their uses in improved network optimization algorithms; M. L. Fredman, R. E. Tarjan, J. ACM 34, 3, pages 596-615 (July 1987) issn 0004-5411
[2] Fast DecreaseKey Heaps with worst-case variants; V. Majerech, https://arxiv.org/abs/2010.02507 eprint 2010.02507 [3] Strict Fibonacci Heaps; G. S. Brodal, G. Lagogiannis, R. E. Tarjan, ACM Trans. Algorithms 21, 2, Article 15 (January 2025) issn 1549-6325 |