Enumeration Algorithms Using Structure

Description and Aim

Enumeration is at the heart of Computer Science and Combinatorics. Traditionally algorithms for enumeration have concentrated on output sensitive analysis to assess efficiency. During the last decade exact exponential time algorithms for enumeration have been emerging with input sensitive analysis for their running time. More recently, some interesting development has shown that it is possible to design algorithms for enumeration that are efficient both in the input and in the output sensitive sense. It is thus a perfect time to join the efforts of the output and input analysis sides to study the interaction between these approaches, and design algorithms that will be of use in practice with running times that are good in both types of analysis.

This is indeed the main goal of this workshop which aims to bring together these two communities.

Enumeration provides a fascinating interface between combinatorial and algorithmic issues.  One of our main aims in this workshop is to approach the difficult task of enumeration using the structure of the input. A lot of attention has been given to exploiting the structure in search of tractability, when it comes to optimization and decision problems. However this track was left largely unexplored when it comes to enumeration problems until recently. During the last few years some promising results have been obtained, which makes it timely to concentrate on enumeration algorithms using the structure of the input.