Cliques in Geometric Graphs, and Application to Overlap Detection for Decision Tables
Organization
Algorithms & Theory
Abstract
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.
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.
Graduation Theses defence year
2016-2017
Supervisor
Dirk Oliver Theis
Spoken language (s)
English
Requirements for candidates
Analysis of algorithms.
Level
Masters
Keywords
Application of contact
Name
Dirk Oliver Theis
Phone
E-mail