8 citations · 9 across the 3 of their papers we have counts for
4 papers
On Polynomial-Time Combinatorial Algorithms for Maximum -Bounded Flow
Kateřina Altmanová, Petr Kolman, Jan Voborník
Given a graph with two distinguished vertices and an integer , an {\em -bounded flow} is a flow between and that can be decomposed into paths of…
On Algorithms for -bounded Cut Problem
Petr Kolman
Given a graph with two distinguished vertices and an integer parameter , an {\em -bounded cut} is a subset of edges (vertices) such that the every…
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…
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…