Lorentz Center

International center for scientific workshops

International center for scientific workshops

Current Workshop | Overview | Back | Home | Search | | ||||||||||

## Enumeration Algorithms Using Structure |

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.
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.
Many interesting
talks and discussions. However
nothing to rank scientific breakthrough.
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.
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. [Back] |