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
Suhtlemiskeel(ed)
inglise keel
Nõuded kandideerijale
Analysis of algorithms.
Tase
Magister
Märksõnad
#tcs

Kandideerimise kontakt

 
Nimi
Dirk Oliver Theis
Tel
E-mail
dotheis@ut.ee