For background information on the topic as a whole, scroll to the end of this page.
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 (Milan Lopuhaä-Zwakenberg) 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.
Heuristics for graph problems (Milan Lopuhaä-Zwakenberg, Yanni Dong) Supervisor: Milan Lopuhaä-Zwakenberg and Yanni Dong
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.
Is your automaton correct? Show me! (Arend Rensink) Supervisor: Arend Rensink
For graph-like models like automata, there are many ways to specify correctness properties, such as "a final state is always reachable" or "after every request action, a reply eventuelly follows". Formalisms in which you can formulate such properties are sometimes collectively called temporal logics, and much research has been done on algorithms for checking them.
The problem addressed by this project is not to prove (or disprove) temporal logic properties, but how to represent a proof that it holds for a given graph - sometimes called a witness for the property. Such a witness may take the form of a path in the graph, but for other logics they have a tree-like structure. There is no common understanding of what constitutes a good notion of witness, let alone how to visualise it.
Contact
Background
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)
