Title: High-performance graph algorithms
Proposer: Hans-Wolfgang Loidl
Suggested supervisors: Hans-Wolfgang Loidl
Goal: The goal is to develop a compact application that has multiple analysis techniques (multiple kernels) accessing a single data structure representing a weighted, undirected graph. In addition to a kernel to construct the graph from the input tuple list, there is one additional computational kernel to operate on the graph.
Description:
Graph algorithms are commonly used in many application domains such as cybersecurity, medical informatics, data enrichment, social networks, and symbolic networks. As these graphs can be huge, it is important to find an efficient data representation and to provide high-performance implementations of common operations, such as breadth-first search [1].
In this project, application kernels should be developed for tunable generation of a random graph and for implementing breadth-first search [2] in this graph. An efficient representation for a sparse graph has to be chosen from the start, and dependencies in the code should be minimised in order to allow parallelisation. Both application kernels should be implemented in an object-oriented language (eg. Java or C#) and in a functional language (eg. Haskell or ML). The performance of both implementations should be evaluated on a range of input graphs.
Resources required: Powerful compute server (as in the department).
Degree of difficulty: Medium
Background needed: Working knowledge in object-oriented and some background in functional programming.
References: