Graphs can be used as effective models in a very diverse range of domains, within and without computer science. When used as such, they form an appealing and intuitive abstraction in which only the essentials of the domain are represented. Based on graph models, their analysis, their transformation and their evolution over time, understanding of and predictions about the systems being modelled ensue.
The topic of graphs leads to projects of varying nature, ranging from theoretical (the study of graph properties and the mechanics of graph transformation) and application-oriented (developing graph-based models for a particular domain, be it chemical, physical, or digital) to implementation (designing and implementing particular analyses or search strategies).
Prerequisites
Related Modules
- Computer Systems for CS (discrete math)
- Discrete Structures and Efficient Algorithms (entire module, most especially the project)
Available Project Proposals
If you are interested in the general topic of Graphs, or if you have your own project idea related to the topic, please contact us directly. Alternatively, you can also work on one of the following concrete project proposals:
Complexity metrics on graph models Supervisor: Milan Lopuhaä-Zwakenberg
Graphs are an essential tool for modeling high-tech systems. The complexity of a graph can be measured in many ways, from simple metrics like the number of nodes and edges, to more complicated ones such as algebraic connectivity and treewidth. The goal of this project is to study which complexity metrics are relevant in modeling: What do measure, and how easy are they to compute? And does a metric actually tell us what we want to know?
Although no company is involved, it is possible to devote (part of) the project to a case study such as Facebook or the Dutch railway system.
An empirical comparison of (approximation) algorithms to find maximum cliques in hypergraphs Supervisor: Faizan Ahmed
Hypergraph is a generalization of the graph data structure in which a subset of vertices represents edges. A clique is a complete hypergraph inside a hypergraph. This project aims to empirically compare existing (approximation) algorithms to find maximum cliques in a hypergraph. The challenge is to create an inventory of existing (approximation) algorithms and collect benchmark data set for this empirical study. It is also interesting to explore various criteria for a comprehensive comparison.
Heuristics for graph problems Supervisor: Hajo Broersma
If you have your own proposal related to heuristics for graph problems, please contact me to discuss the opportunities. The general approach is to study an NP-hard graph problem of your choice and develop heuristics for finding good solutions.
Rule-based game strategies Supervisor: Arend Rensink
Using graph transformation, you can quickly and easily model a (two-person) board game. Every move of the game corresponds to the application of a rule.
GROOVE is a tool that enables the exploration of the state space of such games. It has strategies for depth-first, breadth-first and many more, but none for games.
The core of this assignment is to add an automatic game strategy to GROOVE, based on approaches from the literature such as min-max or deep learning (to be investigated as part of the assignment), and to test their efficacy and performance.
The assignment can be taken up by more than one student, who can collaborate on part of it but should develop their own strategies.
Large-scale graph generation with user-controlled properties
Contact
