Compact I/O-Efficient Graph Representations
| Název práce v češtině: | Kompaktní I/O-efektivní grafové reprezentace |
|---|---|
| Název v anglickém jazyce: | Compact I/O-Efficient Graph Representations |
| Klíčová slova: | teorie grafů, cache-oblivious algoritmy, kompaktní reprezentace, separovatelné grafy |
| Klíčová slova anglicky: | graph theory, cache-oblivious algorithms, compact representation, separable graphs |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | Mgr. Tomáš Gavenčiak, Ph.D. |
| Řešitel: | Bc. Jakub Tětek - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 06.11.2018 |
| Datum zadání: | 07.11.2018 |
| Datum potvrzení stud. oddělením: | 18.04.2019 |
| Datum a čas obhajoby: | 27.06.2019 09:00 |
| Datum odevzdání elektronické podoby: | 12.05.2019 |
| Datum odevzdání tištěné podoby: | 17.05.2019 |
| Datum proběhlé obhajoby: | 27.06.2019 |
| Oponenti: | Mgr. Martin Mareš, Ph.D. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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. |