Petr Kolman
Department of Applied Mathematics, Charles University,
Malostranské nám. 25,
118 00 Praha 1, Czech Republic
last name "at" kam.mff.cuni.cz
+ 420  95155 4155
+ 420  2  5753 1014 (fax)
Office hours: By appointment. Room #225, 2nd floor.
For what I received I passed on to you as of first importance: that Christ
died for our sins according to the Scriptures, that he was buried, that he
was raised on the third day according to the Scriptures, and that he appeared
to Peter, and then to the Twelve. After that, he appeared to more than
five hundred of the brothers at the same time, most of whom are still living,
though some have fallen asleep. Then he appeared to James, then to all the
apostles, and last of all he appeared to me also.
Whether, then, it was I or they, this is what we preach, and this is what you
believed.
Paul of Tarsus, The First Epistle to the Corinthians

Approximating Spanning Tree Congestion on Graphs with Polylog Degree
To appear in Proc. of 35th Int. Workshop on Combinatorial Algorithms (IWOCA), 2024

How to Cut a Ball without Separating: Improved Approximations for Length Bounded Cut [APPROX presentation]
with Eden Chlamtáč
Proc. of 23rd Int. Conf. on Approximation Algorithms for Combinatorial Optimization Problems (APPROX),
pp. 41:141:17, 2020

On PolynomialTime Combinatorial Algorithms for Maximum LBounded Flow
[arXiv version]
[slides]
with Kateřina Altmanová and Jan Voborník,
Journal of Graph Algorithms and Applications, Volume 24, Number 3, pp. 303322, 2020
Preliminary version in: Proc. of Algorithms and Data Structures Symposium (WADS),
pp 14–27, 2019

On Algorithms Employing Treewidth for Lbounded Cut Problems
[arXiv version]
Journal of Graph Algorithms and Applications, Volume 22, Number 2, pp. 177191, 2018

Extension Complexity, MSO Logic, and Treewidth
[arXiv version]
[slides]
with Martin Koutecky and Hans Raj Tiwary,
Discrete Mathematics and Theoretical Computer Science, Volume 22, No. 2, 2020
Preliminary version in Proc. of 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT),
18:118:14, 2016

Extended Formulation for CSP that is Compact
for Instances of Bounded Treewidth
with Martin Koutecky,
The Electronic Journal of Combinatorics, Volume 22, Issue 4,
paper #4.30, 2015

Approximate Duality of Multicommodity Multiroute Flows
and Cuts: Single Source Case
with Christian Scheideler
Proc. of 23 ACMSIAM Symposium on Discrete Algorithms (SODA),
pp. 800810, 2012

Towards Duality of Multiroute Multicommodity Flows and Cuts: Multilevel Ball Growing
with Christian Scheideler
Theory of Computing Systems, Volume 53, Issue 2, pp. 341363, 2013
Preliminary version in: Proc. of 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 129140, 2011

On Fair Edge Deletion Problems
with Bernard Lidicky and JeanSebastien Sereni, 2009

An Approximation Algorithm for Bounded Degree
Deletion
with Tomas Ebenlendr and Jiri Sgall, 2009

On the Complexity of Paths Avoiding Forbidden Pairs
with Ondřej Pangrác
Discrete Applied Mathematics, Volume 157, Issue 13, pp.
28712876, 2009

LengthBounded Cuts and Flows
with Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler,
Ondřej Pangrác, Heiko Schilling and Martin Skutella
ACM Transactions on Algorithms, Volume 7, Issue 1,
Article No. 4, 2010.

Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
with Henning Bruhn, Jakub Černý, Alexander Hall and Jiří Sgall
Theory of Computing, Volume 4, pp. 120, 2008
Preliminary version in: Proc. of 18 ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 855863, 2007

Reversal Distance for Strings with
Duplicates: Linear Time Approximation using Hitting Set
with Tomek Walen
The Electronic Journal of Combinatorics, Volume 14, Issue 1,
paper R50, 2007
Preliminary version in: Proc. of fourth Workshop on Approximation and Online Algorithms (WAOA),
, LNCS 4368, pp. 281291, 2006

Approximating Reversal Distance for
Strings with Bounded Number of Duplicates
with Tomek Walen
Discrete Applied Mathematics, Volume 155, pp. 327336, 2007
Preliminary version in: Proc. of 30 International Symposium on Mathematical Foundations
of Computer Science (MFCS), pp. 580590,
2005

Minimum Common String Partition Problem:
Hardness and Approximations
with Avraham Goldstein
and Jie Zheng
The Electronic Journal of Combinatorics, Volume 12, Issue 1, Sep. 2005,
paper R50
Preliminary version in: Proc. of 15 International Symposium on Algorithms
and Computation (ISAAC), pp. 484495, 2004

The Greedy Algorithm for the Minimum
Common String Partition Problem
with Marek Chrobak
and Jirka Sgall
ACM Transactions on Algorithms, Volume 1, Issue 2, 2005, pp.
350366
Preliminary version in: Proc. of 7 International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX), pp.
8495, 2004.

A Simple Combinatorial Proof of Duality of
Multiroute Flows and Cuts, 2004.
with Amitabha Bagchi,
Amitabh Chaudhary and Jirka Sgall

Crossing number, paircrossing number, and
expansion
with Jirka Matousek
Journal of Combinatorial Theory, Series B, Volume 92, Issue 1, Sep. 2004,
pp. 99113.

Short Length Menger's Theorem and
Reliable Optical Routing
with Amitabha Bagchi and Amitabh Chaudhary
Theoretical Computer Science, Volume 339, Issue 23, June 2005, pp.
315332.
Preliminary version in: Proc. 15 ACM Symposium on Parallel Algorithms and Architectures
(SPAA), revue paper, 2003.

A Note on the Greedy Algorithm for the
Unsplittable Flow Problem
Information Processing Letters, Volume 88, Issue 3, 2003, pp.
101105.

Algorithms for FaultTolerant Routing in
Circuit Switched Networks
with Amitabha Bagchi, Amitabh Chaudhary, and Christian Scheideler
SIAM Journal on Discrete Mathematics, Volume 21, Issue 1, 2007,
pp. 141157
Preliminary version in: Proc. 14 ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2002.

Improved Bounds for the Unsplittable Flow Problem
with Christian Scheideler
Journal of Algorithms, Volume 61, Number 1, 2006, pp. 2044
Preliminary version in: Proc. 13 ACMSIAM Symposium on Discrete Algorithms
(SODA), 2002.

Simple OnLine Algorithms for the Maximum Disjoint Paths Problem
with Christian Scheideler
Algorithmica, Volume 39, Number 3, 2004, pp. 209233.
Preliminary version in: Proc. 13 ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2001.

Optimal Broadcast on Parallel Locality
Models
with Ben Juurlink, Friedhelm Meyer auf der Heide and Ingo Rieping.
Journal of Discrete Algorithms, Volume 1, Issue 2, 2003, pp.
151166.
Preliminary version in: Proc. of 7 Colloquium on Structural Information and
Communication Complexity (SIROCCO), 2000.

Short Disjoint Paths on Hypercubic
Graphs
Technical report, 2000

On nonblocking properties of the Benes network
Proc. of 6 European Symposium on Algorithms (ESA), volume 1461
of Lecture Notes in Computer Science. Springer, 1998.

PRAM lower bound for element distinctness revisited
Sofsem'97: Theory and Practice of Informatics, volume 1338
of Lecture Notes in Computer Science. Springer, 1997.

Searching for edge disjoint paths on hypercubelike topologies
PhD Thesis, Charles University, Prague, 1998.

Complexity of some problems on COMMON PRAM
Masters Thesis, Charles University, Prague, 1995, in Czech.
Oct 2, 2023