49 citations · 185 across the 18 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 8 cited
Extension Complexity, MSO Logic, and Treewidth
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
We consider the convex hull of all satisfying assignments of a given MSO formula on a given graph . We show that there exists an extended formulation of the polytop…
cs.DM2015★ 3 cited
Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems
Jiří Fiala, Tomáš Gavenčiak, Dušan Knop +2
We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neigh…
cs.CC2015
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Petr Kolman, Martin Koutecký
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 bo…