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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

978-1-61197-503-1

ISSN

—

e-ISSN

—

Počet stran výsledku

15

Strana od-do

247-261

Název nakladatele

SIAM

Místo vydání

Philadelphia

Místo konání akce

New Orleans

Datum konání akce

7. 1. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—