ľ¹Ï¸£ÀûÓ°ÊÓ

PLEASE NOTE: If a candidate gives a layman's talk, the livestream will start fifteen minutes earlier.

Networks are found in many scenarios: as a model for roads, social contacts or the internet. Analysing a network is often challenging due to the size of the network. Computers can help using computation and fast algorithms. But which algorithms are suited to analyse which type of network?

To this end, we study different properties of networks and several mathematical problems that arise from network analysis. We abstract networks to graphs, broadly used mathematical models of networks. For many problems it has been shown that no fast algorithms can exist on general graphs. But, this is an incomplete view of the algorithmic landscape: for a simple graph it can be possible to design an efficient algorithm. Which properties must the graph have so that we can find fast algorithms?

An example of such a property that we study is that the graph does not contain a certain pattern, a so-called forbidden pattern. This gives knowledge about the structure of the graph that can be used in an algorithm. For this property we work out in detail the landscape of the ‘Diameter’ problem and study the landscape of the ‘Subset Vertex Cover’ problem, a variant of the well-known ‘Vertex Cover’ problem.

We also study the streaming paradigm, where the graph is presented to us in a stream, and memory-use is a limiting factor instead of computation time. For this paradigm we explore the landscape of ‘Diameter’ and of ‘Independent Set’ and analyse in detail which form the information in the stream should have to solve these problems using little memory.