Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
F. Slivovsky, S. Szeider:
"A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth";
Vortrag: Theory and Applications of Satisfiability Testing,
Alghero, Italien;
03.07.2020
- 10.07.2020; in: "Theory and Applications of Satisfiability Testing - SAT 2020",
LNCS,
12178
(2020),
ISBN: 978-3-030-51824-0;
S. 267
- 276.
Kurzfassung englisch:
The propositional model counting problem (#SAT) is known
to be fixed-parameter-tractable (FPT) when parameterized by the width
k of a given tree decomposition of the incidence graph. The running time
of the fastest known FPT algorithm contains the exponential factor of
4k. We improve this factor to 2k by utilizing fast algorithms for computing
the zeta transform and covering product of functions representing
partial model counts, thereby achieving the same running time as FPT
algorithms that are parameterized by the less general treewidth of the
primal graph. Our new algorithm is asymptotically optimal unless the
Strong Exponential Time Hypothesis (SETH) fails.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-51825-7_19
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_292348.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.