|Current Workshop | Overview||Back | Home | Search ||
Enumeration Algorithms Using Structure
A. Descriptions and aims of workshop
Enumeration is at the heart of Computer Science. Traditional enumeration algorithms use an output-sensitive time analysis. Recently exact exponential time enumeration algorithms using an input-sensitive analysis have been emerging. The main goal of the workshop was to bring the two communities together. Another goal was to discus and study the use of structural input properties when constructing enumeration algorithms.
B. Tangible outcome
The major and long time open problem in algorithmic enumeration is the question whether the minimal transversals of a hypergraph can be enumerated by an output-polynomial algorithm.
Recently it was shown that this question is equivalent to the question whether the minimal dominating sets of a graph can be enumerated by an output-polynomial algorithms. The later problem has been studied for many graph classes. More such results are to be expected.
A major question in input-sensitive enumeration mentioned various times at Leiden was solved recently: the number of minimal connected dominating sets of a graph on n vertices is smaller than 2^n.
C. Scientific breakthrough
Many interesting talks and discussions. However nothing to rank scientific breakthrough.
D. « Aha » moments
While the methods used by the two communities turned out to be very different, input-sensitive and output-sensitive enumeration algorithms can be combined sometimes such as to obtain a kind of optimal enumeration algorithm.
The format of the workshop was perfect for our purposes. The many invited talks and the tutorials allowed to share the knowledge of the two communities. There are more researchers with publications on both types of enumeration algorithms now. The french enumeration community has now an ANR project (ANR = French Research Agency) concentrating on enumeration on graphs and hypergraphs which started in October 2015. One of the ideas of the project is to organize another enumeration workshop at Leiden.
F. Other comments
We were happy with the Lorentz Center and the help in organization, administration etc. we obtained. We compiled a technical report of open problems at the University of Utrecht.