EUVIMEDEUVIMED entdecken
Crossref

Paradigms for Parameterized Enumeration

Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, Heribert Vollmer

Theory of Computing Systems · 2017-05 · 60 (4) · 737-758

DOI: 10.1007/s00224-016-9702-4 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 13.09.2016. Verfasst von Nadia Creignou und 4 weiteren Autor:innen. Die Arbeit wurde bisher 23-mal zitiert (Crossref) und nennt 26 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First, we define formally different notions of efficient enumeration in the context of parameterized complexity: FPT-enumeration and delayFPT. Second, we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least k, where k is the parameter, in the famous Schaefer’s framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set Γ. Given such a formula and an integer k, we are interested in enumerating all the models of the formula that have weight at least k. We obtain a dichotomy classification and prove that, according to the properties of the constraint language Γ, either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

Zitieren

APA

Creignou, N., Meier, A., Müller, J., Schmidt, J., & Vollmer, H. (2017). Paradigms for Parameterized Enumeration. Theory of Computing Systems, 60(4), 737-758. https://doi.org/10.1007/s00224-016-9702-4

Vancouver

Creignou N, Meier A, Müller J, Schmidt J, Vollmer H. Paradigms for Parameterized Enumeration. Theory of Computing Systems. 2017;60(4):737-758. doi:10.1007/s00224-016-9702-4

BibTeX
@article{Creignou2017,
  author = {Creignou, Nadia and Meier, Arne and Müller, Julian-Steffen and Schmidt, Johannes and Vollmer, Heribert},
  title = {Paradigms for Parameterized Enumeration},
  journal = {Theory of Computing Systems},
  year = {2017},
  volume = {60},
  number = {4},
  pages = {737--758},
  doi = {10.1007/s00224-016-9702-4}
}
Kostenlos starten →