|Cliques in Geometric Graphs, and Application to Overlap Detection for Decision Tables|
|Organisatsiooni nimi||Algorithms & Theory|
|Kokkuvõte||This thesis is about the following problem. Given n d-dimensional axis-parallel boxes, produce a list of points representing the areas where a maximal subset of the boxes intersect.|
There is a naive solution to this problem: it can be reduced to identifying all maximal cliques in a graph. There is also a downright dumb algorithm.
In this project, the goal is to
1. Compare the performance of the naive algorithm with that of the dumb algorithm:
1a through average case analysis;
1b by coding and comparing.
2. Design a new (smart) algorithm which makes use of the special structure of the data as boxes, and avoids reduction to the structure-unaware clique enumeration problem.
|Lõputöö kaitsmise aasta||2016-2017|
|Juhendaja||Dirk Oliver Theis|
|Nõuded kandideerijale||Analysis of algorithms.|
|Nimi||Dirk Oliver Theis|