Beating brute force for (quantified) satisfiability of circuits of bounded treewidth

0489223 - MÚ 2019 RIV US eng C - Conference Paper (international conference)
Lokshtanov, D. - Mikhailin, I. - Ramamohan, P. - Pudlák, Pavel
Beating brute force for (quantified) satisfiability of circuits of bounded treewidth.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2018 - (Czumaj, A.), s. 247-261. ISBN 978-1-61197-503-1.
[Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). New Orleans (US), 07.01.2018-10.01.2018]
Institutional support: RVO:67985840
Keywords : algorithmic properties of circuits of bounded treewidth
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.18

We investigate the algorithmic properties of circuits of bounded treewidth. Here the treewidth of a circuit C is defined as the treewidth of the underlying undirected graph of C, after the vertices corresponding to input gates have been removed. Thus, boolean formulae correspond to circuits of treewidth 1.
Permanent Link: http://hdl.handle.net/11104/0283675