Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative (Dagstuhl Seminar 18421)

Authors Henning Fernau, Petr. A. Golovach, Marie-France Sagot and all authors of the abstracts in this report



PDF
Thumbnail PDF

File

DagRep.8.10.63.pdf
  • Filesize: 6.63 MB
  • 24 pages

Document Identifiers

Author Details

Henning Fernau
Petr. A. Golovach
Marie-France Sagot
and all authors of the abstracts in this report

Cite As Get BibTex

Henning Fernau, Petr. A. Golovach, and Marie-France Sagot. Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative (Dagstuhl Seminar 18421). In Dagstuhl Reports, Volume 8, Issue 10, pp. 63-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/DagRep.8.10.63

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 18421 "Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative".  

Enumeration problems require to list all wanted objects  of the input as, e.g., particular subsets of the vertex or edge set of a given graph or particular satisfying assignments of logical expressions.  Enumeration problems arise in a natural way  in various fields of Computer Science, as, e.g., Artificial Intelligence and Data Mining, in Natural Sciences Engineering, Social Sciences, and Biology. The main challenge of the area of enumeration problems is that, contrary to decision, optimization and even counting problems, the output length of an enumeration problem is often exponential in the size of the input and cannot be neglected. This makes enumeration problems more challenging than many other types of algorithmic problems and demands development of specific techniques.

The principal goals of  our Dagstuhl seminar were to increase the visibility of algorithmic enumeration within (Theoretical) Computer Science and to contribute to establishing it as an area of ``Algorithms and Complexity''. The seminar  brought together researchers within the algorithms community, other fields of Computer Science and Computer Engineering, as well as researchers working on enumeration problems in other application areas, in particular Biology. The aim was to   accelerate developments and discus new directions including algorithmic tools and hardness proofs.

Subject Classification

Keywords
  • algorithms
  • input-sensitive enumeration
  • output-sensitive enumeration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail