Erik Jan van Leeuwen

Date: 16:00 – 16:30, Thursday, 28.10.2021
Location: MS Teams ICS Colloquium & Minnaert 2.02

Title:Graph Algorithms: From Application to Parameterization
Abstract:Challenges in networks and graphs can be met by the development of efficient algorithms. In this talk, I will demonstrate how to design such algorithms using graph structure theory, while using modern computational complexity theory as evidence that these algorithms are in some sense best possible. As main examples, I will consider the problem of buying a subnetwork to illustrate the Steiner Tree problem in planar graphs, and the problem of computing the diameter of a graph to discuss computations on data streams. In both cases, we use parameterized complexity for a precise analysis of the complexity of these problems.