Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F18%3A00489223" target="_blank" >RIV/67985840:_____/18:00489223 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1137/1.9781611975031.18" target="_blank" >http://dx.doi.org/10.1137/1.9781611975031.18</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611975031.18" target="_blank" >10.1137/1.9781611975031.18</a>
Alternative languages
Result language
angličtina
Original language name
Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-1-61197-503-1
ISSN
—
e-ISSN
—
Number of pages
15
Pages from-to
247-261
Publisher name
SIAM
Place of publication
Philadelphia
Event location
New Orleans
Event date
Jan 7, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—