Geodesic
Extended formulation for CSP that is compact for instances of bounded treewidth
Petr Kolman1 ; Martin Koutecký1
1Charles University in Prague
The electronic journal of combinatorics, Tome 22 (2015) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 of several important NP-hard problems on graphs of bounded treewidth.
DOI : 10.37236/5474
Classification : 68Q25, 68Q17, 68R10, 90C05
Mots-clés : constraint satisfaction problems, linear programming, extended formulations, parameterized complexity, treewidth

Petr Kolman  1   ; Martin Koutecký  1

1 Charles University in Prague 
@article{10_37236_5474,
     author = {Petr Kolman and Martin Kouteck\'y},
     title = {Extended formulation for {CSP} that is compact for instances of bounded treewidth},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {4},
     doi = {10.37236/5474},
     zbl = {1393.68073},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5474/}
}
TY  - JOUR
AU  - Petr Kolman
AU  - Martin Koutecký
TI  - Extended formulation for CSP that is compact for instances of bounded treewidth
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5474/
DO  - 10.37236/5474
ID  - 10_37236_5474
ER  - 
%0 Journal Article
%A Petr Kolman
%A Martin Koutecký
%T Extended formulation for CSP that is compact for instances of bounded treewidth
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5474/
%R 10.37236/5474
%F 10_37236_5474
Petr Kolman; Martin Koutecký. Extended formulation for CSP that is compact for instances of bounded treewidth. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/5474

Cité par Sources :