Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus
 
 

Bartłomiej Bosek

PhD

phone: (+48) 12 664 75 95
fax: (+48) 12 664 66 72
email: email
office: ul. Prof. S. Łojasiewicza 6, 30-348 Kraków
room: 3150
office hours: Tuesday 14:00 - 15:00
Wednesday 14:00 - 15:00
 
personal homepage
for students
 
msc thesis:[pdf]
phd thesis:[pdf]
photo

research interests
theory of graphs and posets
combinatorial games
on-line algorithms

selected publications
  • Bartłomiej Bosek, Stefan Felsner, Kolja Knauer and Grzegorz Matecki.
    On the Duality of Semiantichains and Unichain Coverings.
    accepted in Order.
  • Bartłomiej Bosek and Tomasz Krawczyk.
    A Subexponential Upper Bound for On-line Chain Partitioning Problem.
    Combinatorica, (2015).
  • Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych.
    Online bipartite matching in offline time.
    In Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS14, pp. 384-393, 2014.
  • Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki and Wiktor Żelazny.
    Additive colorings of planar graphs.
    Graphs and Combinatorics, 30(2014), no. 5, 1087-1098.
  • Bartłomiej Bosek, Tomasz Krawczyk and Grzegorz Matecki.
    First-fit coloring of incomparability graphs.
    SIAM Journal on Discrete Mathematics, 27(2013), no. 1, 126-140.
  • Bartłomiej Bosek, Kamil Kloch, Tomasz Krawczyk and Piotr Micek.
    On-line dimension of semi-orders.
    Order, 30(2013), 593-615.
  • Bartłomiej Bosek, Stefan Felsner, Kolja Knauer and Grzegorz Matecki.
    News about Semiantichains and Unichain Coverings.
    Proceedings of the 7th International Computer Science Symposium in Russia, CSR2012, pp. 43-51, 2012.
  • Bartłomiej Bosek, Piotr Micek, Kamil Kloch and Tomasz Krawczyk.
    On-line Version of Rabinovitch Theorem for Proper Intervals.
    Discrete Mathematics, 23(2012), 3426-3436.
  • Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki and Piotr Micek.
    On-line Chain Partitions of Orders: a Survey.
    Order, 29(2012), 49-73.
  • Bartłomiej Bosek, Leszek Horwath, Grzegorz Matecki and Arkadiusz Pawlik.
    High performance GPGPU based system for matching people in a live video feed.
    In Proceedings of the 3rd International Conference on Image Processing Theory, Tools and Applications, IPTA2012, pp. 448-453, 2012.
  • Bartłomiej Bosek, Tomasz Krawczyk and Grzegorz Matecki.
    Forbidden Structures for Efficient First-Fit Chain Partitioning (extended abstract).
    Electronic Notes in Discrete Mathematics, 38(2011), 173-179, proc. EuroComb 2011.
  • Bartłomiej Bosek, Tomasz Krawczyk.
    The sub-exponential upper bound for on-line chain partitioning problem.
    In Proceedings of the 51th Symposium on Foundations of Computer Science, FOCS10, pp. 347-354, 2010.
  • Bartłomiej Bosek, Tomasz Krawczyk and Edward Szczypka.
    First-Fit algorithm for on-line chain partitioning problem.
    SIAM Journal on Discrete Mathematics, 23(2010), no. 4, 1992-1999.
  • Patrick Baier, Bartłomiej Bosek and Piotr Micek.
    On-line Chain Partitioning of Up-growing Interval Orders.
    Order, 24(2007), 1-13.
  • Bartłomiej Bosek and Piotr Micek.
    On-line Adaptive Chain Covering of Upgrowing Posets.
    Discrete Mathematics and Theoretical Computer Science Proceedings, AF(2006), 37-48.
  • Bartłomiej Bosek and Piotr Micek.
    Variants of Online Chain Partition Problem of Posets.
    Electronic Notes in Theoretical Computer Science, 140(2005), 3-13.

  • some recent collaborators 
    Stefan FelsnerTechnische Universität Berlin, Institut für Mathematik
    Jarosław GrytczukJagiellonian University, Wydział Matematyki i Informatyki
    Kolja KnauerTechnische Universität Berlin, Institut für Mathematik
    Tomasz KrawczykJagiellonian University, Wydział Matematyki i Informatyki
    Grzegorz MateckiJagiellonian University, Wydział Matematyki i Informatyki
    Wiktor ŻelaznyJagiellonian University, Wydział Matematyki i Informatyki

    grants
    2007 - 2008 On-line Chain Partitioning Approach to Scheduling
      Ministry of Science and Higher Education
      N206 2729 33
    2010 - 2012 On-line algorithms and combinatorial games
      Ministry of Science and Higher Education
      N206 4923 38
    2010 - 2012 Movement tracking in monitored zones
      Ministry of Science and Higher Education
      R00 0081 11
    2012 - 2014 Coloring games on graphs and partially ordered sets
      Polish National Science Center
      MO-2011/03/B/ST6/01367
    2014 - 2017 On new techniques for matching and flow problems
      Polish National Science Center
      UMO-2013/11/D/ST6/03100

    short cv
    2004Master of Science in Computer ScienceJagiellonian UniversityKrakow, Poland
    2008Philosophy Doctor in MathematicsJagiellonian UniversityKrakow, Poland
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl