Springe direkt zu Inhalt

Viktoriya Kraleva:

Robust algorithms for finding a triangle in abstractly given unit disk graphs in polynomial time


Today, cellular networks are a vital component of our day-to-day life, due to the inevitable requirements to technology to have wireless capabilities. An oversimplified theoretical model for cellular networks are unit disk graphs. One of the most uncomplicated, yet most popular problems, concerning graphs, is the triangle detection problem. In this thesis, a robust algorithms model is used, combined with the kissing property of unit disk graphs, in order to construct robust algorithms for finding a triangle in unit disk graphs, given in abstract graph form, which run in polynomial time. The correctness of the approach is proven theoretically and the running time is evaluated with the help of O-Notation for two possible graph representations - adjacency list and adjacency matrix. Furthermore, for each graph representation a Python implementation is introduced. With the help of the implementation, the execution time of the algorithms is evaluated empirically. Different data sets from several graph classes are created, in order to gain a better understanding of the running time dependency on the input. The data sets are parameterized with values, which could affect the running time, like number of vertices, sample size, axis bounds and edge inclusion probabilities. Eventually, linear plots are visualized, comparing the sample mean and the sample standard deviation of the running time of the algorithm for data sets, consisting of different graph classes and represented in different abstract forms.

Bachelor of Science (B.Sc.)