Hans Bodlaender

Date: 16:00 – 17:00, Friday, 04.10.2019
Location: Minnaert – 2.02

Title: Trees, TSPs and Terrorists
Abstract: How hard can it be for a computer to compute something? Theoretical and experimental algorithm research aims at answering this question, from a large number of angles. One of these angles is that of parameterized complexity: what if one aspect of the input of our problem can be considered to be small. The talk will introduce the members of the algorithms and complexity group, survey a few central notions of parameterized complexity, and then sketch two results: Shapley values of nodes in networks with small treewidth can be computed efficiently; this is applied to determining in a certain model the “importance” of terrorists in their social network, and we establish the exact asymptotic complexity of the Traveling Salesman Problem for points in space with Euclidean distances.
(Joint work with Tom van der Zanden, Sandor Kisfaludi-Bak and others.)