arvutiteaduse instituudi lõputööde teemade register

Cliques in Geometric Graphs, and Application to Overlap Detection for Decision Tables
Organisatsiooni nimiAlgorithms & Theory
KokkuvõteThis 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 aasta2016-2017
JuhendajaDirk Oliver Theis
Suhtlemiskeel(ed)inglise keel
Nõuded kandideerijaleAnalysis of algorithms.
Tase Magister
Märksõnad #tcs
Kandideerimise kontakt
Nimi Dirk Oliver Theis