Zobrazeno 1 - 10
of 122
pro vyhledávání: '"Kolman, Petr"'
Autor:
Kolman, Petr
The {\em Spanning Tree Congestion} problem is an easy-to-state NP-hard problem: given a graph $G$, construct a spanning tree $T$ of $G$ minimizing its maximum edge congestion where the congestion of an edge $e\in T$ is the number of edges $uv$ in $G$
Externí odkaz:
http://arxiv.org/abs/2410.00568
Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer $L$, an {\em $L$-bounded flow} is a flow between $s$ and $t$ that can be decomposed into paths of length at most $L$. In the {\em maximum $L$-bounded flow problem} the
Externí odkaz:
http://arxiv.org/abs/1902.07568
Autor:
Kolman, Petr
Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer parameter $L>0$, an {\em $L$-bounded cut} is a subset $F$ of edges (vertices) such that the every path between $s$ and $t$ in $G\setminus F$ has length more than $L$. T
Externí odkaz:
http://arxiv.org/abs/1705.02390
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 22 no. 4, Discrete Algorithms (October 1, 2020) dmtcs:5583
We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments of a given MSO formula $\varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{\varphi}(G)$ that can be described by $f(|\varphi|
Externí odkaz:
http://arxiv.org/abs/1507.04907
Autor:
Kolman, Petr, Koutecký, Martin
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
Externí odkaz:
http://arxiv.org/abs/1502.05361
Autor:
Kolman Petr
Publikováno v:
Central European Journal of Public Policy, Vol 16, Iss 2, Pp 64-65 (2022)
Externí odkaz:
https://doaj.org/article/1c471b55b46b45f68438415f2f426af3
Publikováno v:
Listy; 2024, Issue 3, p4-6, 3p