Algorithmics Research Group

Theoretical Computer Science
Faculty of Mathematics and Computer Science
Jagiellonian University

Algorithmics Research Group

Bartłomiej Bosek

PhD

phone:	(+48) 12 664 75 95
fax:	(+48) 12 664 66 72
email:
office:	ul. Prof. S. Łojasiewicza 6, 30-348 Kraków
room:	3150
office hours:	Wednesday 15:00 - 16:00

personal homepage
for students

msc thesis:	[pdf]
phd thesis:	[pdf]

research interests

theory of graphs and posets

combinatorial games

on-line algorithms

selected publications

Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki and Wiktor Żelazny.
Additive colorings of planar graphs.
submitted.

Bartłomiej Bosek and Tomasz Krawczyk.
A Subexponential Upper Bound for On-line Chain Partitioning Problem.
submitted.

Bartłomiej Bosek, Piotr Micek, Kamil Kloch and Tomasz Krawczyk.
On-line dimension of semi-orders.
accepted in Order.

Bartłomiej Bosek, Piotr Micek, Kamil Kloch and Tomasz Krawczyk.
On-line Version of Rabinovitch Theorem for Proper Intervals.
accepted in Discrete Mathematics.

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, Stefan Felsner, Kolja Knauer and Grzegorz Matecki.
News about Semiantichains and Unichain Coverings.
accepted to CSR 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
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.

Bartłomiej Bosek and Piotr Micek.
On-line Dimension of Up-growing Posets.
manuscript, (2005).

some recent collaborators
Stefan Felsner	Technische Universität Berlin, Institut für Mathematik
Jarosław Grytczuk	Jagiellonian University, Wydział Matematyki i Informatyki
Kolja Knauer	Technische Universität Berlin, Institut für Mathematik
Tomasz Krawczyk	Jagiellonian University, Wydział Matematyki i Informatyki
Grzegorz Matecki	Jagiellonian University, Wydział Matematyki i Informatyki
Wiktor Żelazny	Jagiellonian 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

short cv
2004	Master of Science in Computer Science	Jagiellonian University	Krakow, Poland
2008	Philosophy Doctor in Mathematics	Jagiellonian University	Krakow, Poland

webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl