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
Office hours: Tuesday 10 - 11am, or by appointment. Malostranské nám. 25, 2nd floor, room #225.
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
-
Bond Polytope under Vertex- and Edge-sums
with Hans R. Tiwary
Manuscript, 2024
-
A Note on Approximation of Spanning Tree Congestion
Accepted for STACS 2025
-
Approximating Spanning Tree Congestion on Graphs with Polylog Degree
[slides]
Proc. of 35th Int. Workshop on Combinatorial Algorithms (IWOCA),
pp. 497-508, 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:1-41:17, 2020
-
On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow
[arXiv version]
[slides]
with Kateřina Altmanová and Jan Voborník,
Journal of Graph Algorithms and Applications, Volume 24, Number 3, pp. 303-322, 2020
Preliminary version in: Proc. of Algorithms and Data Structures Symposium (WADS),
pp 14–27, 2019
-
On Algorithms Employing Treewidth for L-bounded Cut Problems
[arXiv version]
Journal of Graph Algorithms and Applications, Volume 22, Number 2, pp. 177-191, 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:1-18: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 ACM-SIAM Symposium on Discrete Algorithms (SODA),
pp. 800-810, 2012
-
Towards Duality of Multiroute Multicommodity Flows and Cuts: Multilevel Ball Growing
with Christian Scheideler
Theory of Computing Systems, Volume 53, Issue 2, pp. 341-363, 2013
Preliminary version in: Proc. of 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 129-140, 2011
-
On Fair Edge Deletion Problems
with Bernard Lidicky and Jean-Sebastien 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.
2871-2876, 2009
-
Length-Bounded 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. 1-20, 2008
Preliminary version in: Proc. of 18 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 855-863, 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. 281-291, 2006
-
Approximating Reversal Distance for
Strings with Bounded Number of Duplicates
with Tomek Walen
Discrete Applied Mathematics, Volume 155, pp. 327-336, 2007
Preliminary version in: Proc. of 30 International Symposium on Mathematical Foundations
of Computer Science (MFCS), pp. 580-590,
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. 484-495, 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.
350-366
Preliminary version in: Proc. of 7 International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX), pp.
84-95, 2004.
-
A Simple Combinatorial Proof of Duality of
Multiroute Flows and Cuts, 2004.
with Amitabha Bagchi,
Amitabh Chaudhary and Jirka Sgall
-
Crossing number, pair-crossing number, and
expansion
with Jirka Matousek
Journal of Combinatorial Theory, Series B, Volume 92, Issue 1, Sep. 2004,
pp. 99-113.
-
Short Length Menger's Theorem and
Reliable Optical Routing
with Amitabha Bagchi and Amitabh Chaudhary
Theoretical Computer Science, Volume 339, Issue 2-3, June 2005, pp.
315-332.
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.
101-105.
-
Algorithms for Fault-Tolerant Routing in
Circuit Switched Networks
with Amitabha Bagchi, Amitabh Chaudhary, and Christian Scheideler
SIAM Journal on Discrete Mathematics, Volume 21, Issue 1, 2007,
pp. 141-157
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. 20-44
Preliminary version in: Proc. 13 ACM-SIAM Symposium on Discrete Algorithms
(SODA), 2002.
-
Simple On-Line Algorithms for the Maximum Disjoint Paths Problem
with Christian Scheideler
Algorithmica, Volume 39, Number 3, 2004, pp. 209-233.
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.
151-166.
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 hypercube-like topologies
PhD Thesis, Charles University, Prague, 1998.
-
Complexity of some problems on COMMON PRAM
Masters Thesis, Charles University, Prague, 1995, in Czech.
Oct 30, 2024
