Fixed parameter tractable optimization under DNNF constraints

DOI10.3233/978-1-61499-672-9-1194MaRDI QIDQ4576242zbMATH OpenFDO

Authors Frédéric Koriche, Daniel Le Berre, Emmanuel Lonca, Pierre Marquis

Publication date 12 July 2018

Full work available at URL https://doi.org/10.3233/978-1-61499-672-9-1194

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Decomposable negation normal form
• On compiling CNFs into structured deterministic DNNFs
• Compiling CP subproblems to MDDs and d-DNNFs
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Parameterized compilation lower bounds for restricted CNF-formulas

This page was built for publication: Fixed parameter tractable optimization under DNNF constraints

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