Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Paradigms for Parameterized Enumeration
CNRS, Aix-Marseille Université, France.
Institut für Theoretische Informatik, Gottfried Wilhelm Leibniz Universität, Germany.
Institut für Theoretische Informatik, Gottfried Wilhelm Leibniz Universität, Germany.
Department of Computer and Information Science, Linköping University, Sweden.
Visa övriga samt affilieringar
2017 (Engelska)Ingår i: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 60, nr 4, s. 737-758Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

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.

Ort, förlag, år, upplaga, sidor
Springer, 2017. Vol. 60, nr 4, s. 737-758
Nyckelord [en]
Parameterized complexity, Kernel, Enumeration, Parameterized enumeration, Algorithms, Self-reducibility
Nationell ämneskategori
Data- och informationsvetenskap Diskret matematik
Identifikatorer
URN: urn:nbn:se:hj:diva-34361DOI: 10.1007/s00224-016-9702-4ISI: 000399178400007Scopus ID: 2-s2.0-84987638662OAI: oai:DiVA.org:hj-34361DiVA, id: diva2:1057829
Anmärkning

A preliminary version of this paper appeared in the proceedings of MFCS 2013, LNCS 8087, pp. 290–301.

Tillgänglig från: 2016-12-19 Skapad: 2016-12-19 Senast uppdaterad: 2018-01-13Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Schmidt, Johannes

Sök vidare i DiVA

Av författaren/redaktören
Schmidt, Johannes
I samma tidskrift
Theory of Computing Systems
Data- och informationsvetenskapDiskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 133 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf