In graph theory a graph represents the interconnection of a set of objects (i.e., nodes) through edges. A directed graph is a graph where the edges assume directions. Directed graphs are prevalent in scientific and engineering disciplines such as communication systems, biological systems and social networks. An important concept of directed graphs is reachability, which is a binary relation on the node set specifying that node i can reach node j if and only if there is a directed path from i to j in the graph. For some applications two graphs are considered “equivalent” if they have the same reachability. In this project we plan to study the problem of finding the minimum equivalent graph of a given finite directed graph. Specifically, for a given directed graph, we seek a reduced equivalent graph with the same node set but with the number of edges minimized. We consider two cases distinguished by whether or not the edge set of the reduced equivalent graph is a subset of the given graph. The expected outcome of the project is the development of the algorithms to solve the graph simplification problems, as well as the implementation of the algorithms on a suitable platform (e.g., MATLAB or C). Through the project the participants will develop some theoretical understanding of graph theory and complexity theory. As one of the problem is NP-hard, the participants can experiment with combinatorial optimization algorithms such as branch-and-bound or approximate algorithms.
There is no specific requirement to undertake this project, though knowledge of graphs and algorithms is certainly helpful. Also, familiarity with programming language or MATLAB is an advantage for the implementation part later in the project. Students can contact Dr. Kin Cheong Sou for more information if they have concern about the project.
Obs! För GU-studenter räknas projektet som ett projekt i Tillämpad Matematik (MMG900/MMG920).
Examinator Maria Roginskaya
Institution Matematiska vetenskaper