A complexity theory for hard enumeration problems

DOI10.1016/J.DAM.2019.02.025MaRDI QIDQ6828217zbMATH OpenFDO

Authors Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, Heribert Vollmer

Publication date 19 September 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2019.02.025

zbMATH Keywords

computational complexityenumerationcomplexity classesreductions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited in

(8)

• Enumerating minimal connected dominating sets
• Enumerating minimal connected dominating sets
• Identifying roles of formulas in inconsistency under Priest's minimally inconsistent logic of paradox
• Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
• Enumeration classes defined by circuits
• Roman hitting functions
• On the complexity of enumerating ordered sets
• Foundations of block-parallel automata networks

This page was built for publication: A complexity theory for hard enumeration problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828217)