Computations on Networks with a Tree-Structure: From Theory to Practice

Samenvatting

Dynamic programming based on tree decomposition is one of the most successful approaches for solving important hard problems on networks, with problems ranging from several application areas (including operations research, computational biology, etc.). In theory, Bodlaender's algorithm and Courcelle's theorem give for a large collection of problems algorithms that solve them in time linear in the number of vertices, assuming we have a graph or network with the appropriate structure (i.e., the treewidth is bounded); a condition that appears to be true for many networks from quite various applications.

However, while these results and the corresponding algorithms play a central role in many theoretical / foundational studies, and are seen as cornerstones in the field of parameterized algorithms (“fixed parameter tractability”), the direct practical use is under debate: while asymptotic optimal, the constant factors hidden in the big-Oh notation are huge. Thus, a worthy topic of study is to see how the theoretical results can be moved to useful practical results. This asks for the development of new algorithmic insights and algorithm engineering studies, alongside with further insights in the structure of networks that allow these type of dynamic programming algorithms.

Both Japan and the Netherlands have strong and well known researchers in this area. This seminar brings together these experts to initiate new studies towards significant progress both in practice as in theory.

Kenmerken

Projectnummer

040.40.008

Hoofdaanvrager

Dr. H.L. Bodlaender

Verbonden aan

Universiteit Utrecht, Faculteit Bètawetenschappen, Departement Informatica

Looptijd

17/09/2018 tot 23/09/2018