Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10312822" target="_blank" >RIV/00216208:11320/15:10312822 - isvavai.cz</a>
Výsledek na webu
<a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p30" target="_blank" >http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p30</a>
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Popis výsledku v původním jazyce
In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity ofseveral important NP-hard problems on graphs of bounded treewidth.
Název v anglickém jazyce
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Popis výsledku anglicky
In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity ofseveral important NP-hard problems on graphs of bounded treewidth.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—

Projekt
<a href="/cs/project/GA14-10003S" target="_blank" >GA14-10003S: Omezené typy výpočtů: algoritmy, modely, složitost</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění
2015
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ů

Podobné výsledky(10)