Petr Kolman

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 9

Top Topics

Highly Parallelizable

Decision Problems

Tractable Cases

Monadic Datalog

Top Venues

J. Graph Algorithms Appl.

Publications

Petr Kolman
Approximating Spanning Tree Congestion on Graphs with Polylog Degree. IWOCA (2024)
Katerina Altmanová, Petr Kolman, Jan Voborník
On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow. J. Graph Algorithms Appl. 24 (3) (2020)
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
Extension Complexity, MSO Logic, and Treewidth. Discret. Math. Theor. Comput. Sci. 22 (4) (2020)
Eden Chlamtác, Petr Kolman
How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut. APPROX-RANDOM (2020)
Katerina Altmanová, Petr Kolman, Jan Voborník
On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow. CoRR (2019)
Katerina Altmanová, Petr Kolman, Jan Voborník
On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow. WADS (2019)
Petr Kolman
On Algorithms Employing Treewidth for L-bounded Cut Problems. J. Graph Algorithms Appl. 22 (2) (2018)
Petr Kolman
On Algorithms for $L$-bounded Cut Problem. CoRR (2017)
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
Extension Complexity, MSO Logic, and Treewidth . SWAT (2016)
Petr Kolman, Martin Koutecký
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth. CoRR (2015)
Petr Kolman, Martin Koutecký
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth. Electron. J. Comb. 22 (4) (2015)
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
Extension Complexity, MSO Logic, and Treewidth. CoRR (2015)
Petr Kolman, Christian Scheideler
Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. Theory Comput. Syst. 53 (2) (2013)
Petr Kolman, Christian Scheideler
Approximate duality of multicommodity multiroute flows and cuts: single source case. SODA (2012)
Petr Kolman, Christian Scheideler
Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. STACS (2011)
Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling, Martin Skutella
Length-bounded cuts and flows. ACM Trans. Algorithms 7 (1) (2010)
Petr Kolman, Ondrej Pangrác
On the complexity of paths avoiding forbidden pairs. Discret. Appl. Math. 157 (13) (2009)
Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman, Jirí Sgall
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks. Theory Comput. 4 (1) (2008)
Amitabha Bagchi, Amitabh Chaudhary, Christian Scheideler, Petr Kolman
Algorithms for Fault-Tolerant Routing in Circuit-Switched Networks. SIAM J. Discret. Math. 21 (1) (2007)
Petr Kolman, Tomasz Walen
Approximating reversal distance for strings with bounded number of duplicates. Discret. Appl. Math. 155 (3) (2007)
Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman
Single source multiroute flows and cuts on uniform capacity networks. SODA (2007)
Petr Kolman, Tomasz Walen
Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set. Electron. J. Comb. 14 (1) (2007)
Petr Kolman, Tomasz Walen
Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set. WAOA (2006)
Petr Kolman, Christian Scheideler
Improved bounds for the unsplittable flow problem. J. Algorithms 61 (1) (2006)
Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman
Short length Menger's theorem and reliable optical routing. Theor. Comput. Sci. 339 (2-3) (2005)
Avraham Goldstein, Petr Kolman, Jie Zheng
Minimum Common String Partition Problem: Hardness and Approximations. Electron. J. Comb. 12 (2005)
Marek Chrobak, Petr Kolman, Jirí Sgall
The greedy algorithm for the minimum common string partition problem. ACM Trans. Algorithms 1 (2) (2005)
Petr Kolman
Approximating Reversal Distance for Strings with Bounded Number of Duplicates. MFCS (2005)
Petr Kolman, Jirí Matousek
Crossing number, pair-crossing number, and expansion. J. Comb. Theory, Ser. B 92 (1) (2004)
Petr Kolman, Christian Scheideler
Simple On-Line Algorithms for the Maximum Disjoint Paths Problem. Algorithmica 39 (3) (2004)
Avraham Goldstein, Petr Kolman, Jie Zheng
Minimum Common String Partition Problem: Hardness and Approximations. ISAAC (2004)
Marek Chrobak, Petr Kolman, Jirí Sgall
The Greedy Algorithm for the Minimum Common String Partition Problem. APPROX-RANDOM (2004)
Ben H. H. Juurlink, Petr Kolman, Friedhelm Meyer auf der Heide, Ingo Rieping
Optimal broadcast on parallel locality models. J. Discrete Algorithms 1 (2) (2003)
Petr Kolman
A note on the greedy algorithm for the unsplittable flow problem. Inf. Process. Lett. 88 (3) (2003)
Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman
Short length menger's theorem and reliable optical routing. SPAA (2003)
Amitabha Bagchi, Amitabh Chaudhary, Christian Scheideler, Petr Kolman
Algorithms for fault-tolerant routing in circuit switched networks. SPAA (2002)
Petr Kolman, Christian Scheideler
Improved bounds for the unsplittable flow problem. SODA (2002)
Petr Kolman, Christian Scheideler
Simple on-line algorithms for the maximum disjoint paths problem. SPAA (2001)
Ben H. H. Juurlink, Petr Kolman, Friedhelm Meyer auf der Heide, Ingo Rieping
Optimal broadcast on parallel locality models. SIROCCO (2000)
Petr Kolman
On Nonblocking Properties on the Benes Network. ESA (1998)
Petr Kolman
PRAM Lower Bound for Element Distinctness Revisited. SOFSEM (1997)