| 2025 | STACS | Approximation of Spanning Tree Congestion Using Hereditary Bisection. | Petr Kolman |
| 2024 | IWOCA | Approximating Spanning Tree Congestion on Graphs with Polylog Degree. | Petr Kolman |
| 2019 | WADS | On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow. | Katerina Altmanov, Petr Kolman, Jan Vobornk |
| 2012 | SODA | Approximate duality of multicommodity multiroute flows and cuts: single source case. | Petr Kolman, Christian Scheideler |
| 2011 | STACS | Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. | Petr Kolman, Christian Scheideler |
| 2007 | SODA | Single source multiroute flows and cuts on uniform capacity networks. | Henning Bruhn, Jakub Cern, Alexander Hall, Petr Kolman |
| 2006 | WAOA | Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set. | Petr Kolman, Tomasz Walen |
| 2005 | MFCS | Approximating Reversal Distance for Strings with Bounded Number of Duplicates. | Petr Kolman |
| 2004 | ISAAC | Minimum Common String Partition Problem: Hardness and Approximations. | Avraham Goldstein, Petr Kolman, Jie Zheng |
| 2003 | SPAA | Short length menger's theorem and reliable optical routing. | Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman |
| 2002 | SODA | Improved bounds for the unsplittable flow problem. | Petr Kolman, Christian Scheideler |
| 2002 | SPAA | Algorithms for fault-tolerant routing in circuit switched networks. | Amitabha Bagchi, Amitabh Chaudhary, Christian Scheideler, Petr Kolman |
| 2001 | SPAA | Simple on-line algorithms for the maximum disjoint paths problem. | Petr Kolman, Christian Scheideler |
| 2000 | SIROCCO | Optimal broadcast on parallel locality models. | Ben H. H. Juurlink, Petr Kolman, Friedhelm Meyer auf der Heide, Ingo Rieping |
| 1998 | ESA | On Nonblocking Properties on the Benes Network. | Petr Kolman |
| 1997 | SOFSEM | PRAM Lower Bound for Element Distinctness Revisited. | Petr Kolman |