Succinct encodings of trees

• Thesis title in Czech: Stručná kódování stromů
• Thesis title in English: Succinct encodings of trees
• Key words: stromy, stručné datové struktury, korektní uzávorkování, stromové pokrytí
• English key words: trees, succinct data structures, blanaced parentheses, tree covering
• Academic year of topic announcement: 2015/2016
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Mareš, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 19.11.2015
• Date of assignment: 20.11.2015
• Confirmed by Study dept. on: 01.12.2015
• Date and time of defence: 12.09.2016 09:00
• Date of electronic submission: 28.07.2016
• Date of submission of printed version: 28.07.2016
• Date of proceeded defence: 12.09.2016
• Opponents: Mgr. Vladan Majerech, Dr.

Guidelines

Stručné (succinct) říkáme těm datovým strukturám, kterým stačí prostor blízký k informačně-teoretickému optimu, a přitom stále mají příznivou časovou složitost vhodné množiny operací.

Cílem práce je prozkoumat existující stručné datové struktury pro reprezentaci stromů, porovnat jejich chování a případně je vylepšit.

References

Sadakane, Kunihiko, and Navarro: Fully-functional succinct trees. In: Proceedings of the 21st annual ACM-SIAM symposium on Discrete Algorithms, 2010.

Pătraşcu: Succincter. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008.

Dodis, Pătraşcu, Thorup: Changing base without losing space. In: Proceedings of the 42th ACM Symposium on Theory of Computing, 2010.