Randomized and approximation algorithms Seminar

Tuesday: 16:15 - 17:45, room 0083

Seminarium magisterskie poświęcone nasŧepującym zagadnieniom:
1) Gry strategiczne na grafach - rozgrywana liczba kolorująca, chromatyczna i zachłanna.
2) Geometryczne grafy przecięć (problemy rozpoznawania i rozszerzania częściowych reprezentacji).
3) Algorytmy kolorowania grafów z list, w tym kolorowanie z list on-line (paintability of graphs) i algorytmy strumieniowe (streaming algorithms).
4) Randomizowane algorytmy kolorowania hipergrafów.

Poprzednie referaty

14.04.2015
Maciej Solon
Graphs defined by forbidden patterns.
 
13.01.2015
Andrzej Dorobisz.
Treewidth. Courcelle's theorem.
 
16.12.2014
Grzegorz Gutowski.
s-t orientations of planar graphs.
 
02.12.2014
Andrzej Dorobisz
Treewidth.
 
25.11.2014
18.11.2014,Patryk Mikos
Kernelization and Linear Programming Techniques
 
03.06.2014
M. Solon, P. Wójcik
Polynomial coloring of 3-colorable graphs.
 
27.05.2014
20.05.2014
13.05.2014
Adam Gągol
Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma (by Harris and Srinivasan)

 
References:
David G. Harris, Aravind Srinivasan, Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma, STOC '13

15.04.2014
Grzegorz Gutowski, Jakub Kozik
Lower bounds for on-line graph colorings (cont.)
(join work with P. Micek and X. Zhu)  
08.04.2014
01.04.2014,
Cancelled (all participants are invited to the lecture of prof. A. Ruciński.)
 
18.03.2014
Grzegorz Gutowski, Jakub Kozik
Lower bounds for on-line graph colorings
(join work with P. Micek and X. Zhu)  
04.03.2014
Igor Adamski
Outer-string graphs are chi-bounded
 
References:
Alexandre Rok, Bartosz Walczak, Outer-string graphs are chi-bounded, preprint
21.01.2014
Maciej Solon
On the number of edges in families of pseudo-discs
 
References:
Piotr Micek, Rom Pinchasi, On the number of edges in families of pseudo-discs, preprint
14.01.2014
Maciej Bendkowski
List Colouring When The Chromatic Number Is Close To the Order Of The Graph
 
References:
B. Reed, B. Sudakov, List Colouring When The Chromatic Number Is Close To the Order Of The Graph, Combinatorica December 2004, Volume 25, Issue 1, pp 117-123
07.01.2014
Aneta Pawłowska
Three Topics in Online List Coloring
 
References:
J. Carraher, S. Loeb, T. Mahoney, G. Puleo, M. Tsai, D.B. West,Three Topics in Online List Coloring, preprint
17.12.2013
10.12.2013,Damian Królik
Sum-paintability of generalized theta-graphs
 
References:
J. Carraher, T. Mahoney, G.J. Puleo, D.B. West , Sum-paintability of generalized theta-graphs, preprint
26.11.2013
Wojciech Łopata
Conflict-Free Colourings of Uniform Hypergraphs With Few Edges
 
References:
A.V. Kostochka, M. Kumbhat, T. Łuczak, Conflict-Free Colourings of Uniform Hypergraphs With Few Edges, Combinatorics, Probability and Computing Volume 21 Issue 4, July 2012
12.11.2013
Tomasz Krawczyk, Bartosz Walczak
Coloring subtree overlap graphs with O(log lgo n) colors.
 
05.11.2013
Grzegorz Guśpiel
On the construction of 3-chromatic hypergraphs with few edges.
 
References:
Heidi Gebauer, On the construction of 3-chromatic hypergraphs with few edges, JCTA 120 (2013)