Compact I/O-Efficient Graph Representations

• Thesis title in Czech: Kompaktní I/O-efektivní grafové reprezentace
• Thesis title in English: Compact I/O-Efficient Graph Representations
• Key words: teorie grafů, cache-oblivious algoritmy, kompaktní reprezentace, separovatelné grafy
• English key words: graph theory, cache-oblivious algorithms, compact representation, separable graphs
• Academic year of topic announcement: 2018/2019
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Tomáš Gavenčiak, Ph.D.
• Author: Bc. Jakub Tětek - assigned and confirmed by the Study Dept.
• Date of registration: 06.11.2018
• Date of assignment: 07.11.2018
• Confirmed by Study dept. on: 18.04.2019
• Date and time of defence: 27.06.2019 09:00
• Date of electronic submission: 12.05.2019
• Date of submission of printed version: 17.05.2019
• Date of proceeded defence: 27.06.2019
• Opponents: Mgr. Martin Mareš, Ph.D.

Guidelines

The student will research data structures and algorithms for both cache- and memory-efficient representation of selected classes of graphs and related data structures. The work is of theoretical nature; the aim of the work is to gain deep understanding of the area and major recent results, and to try to obtain improvements in selected subproblems. The work should be focused on the obtained theoretical results. The preferred language of the work is English.

References

Alok Aggarwal, Ashok K Chandra, and Marc Snir. Hierarchical memory with block transfer. In Foundations of Computer Science, pages 204–216. IEEE, 1987.

Daniel K Blandford, Guy E Blelloch, and Ian A Kash. Compact representations of separable graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete
algorithms, pages 679–688. SIAM, 2003.

Erik Demaine. Cache-oblivious algorithms and data structures. In Lecture Notes from the EEF Summer School on Massive Data Sets, 2002.

Craig Dillabaugh, Meng He, and Anil Maheshwari. Succinct and I/O efficient data structures for traversal in trees. Algorithmica, 63(1):201–223, Jun 2012. ISSN 1432-0541. doi:
10.1007/s00453-011-9528-z.