Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Theoretical Computer Science
at Jagiellonian
 
 
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.
table edited by: Jakub Kozik
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)
  •  
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl