2014/2015

10.06
 Tomasz Krawczyk (Uniwersytet Jagielloński)
 On-line approach to off-line coloring problems on graphs with geometric representations

The main goal of this talk is to present and explore a connection between chromatic properties of graphs with geometric representations and competitive analysis of on-line algorithms, which became apparent after the recent construction of triangle-free geometric intersection graphs with arbitrarily large chromatic number due to Pawlik et al. We show that on-line graph coloring problems give rise to classes of game graphs with a natural geometric interpretation.
We use this concept to estimate the chromatic number of graphs with geometric representations by finding, for appropriate simpler graphs, on-line coloring algorithms using few colors or proving that no such algorithms exist.

We illustrate the above mention technique with two examples. First we show how to use on-line coloring of cocomparability graphs to bound the chromatic number of interval filament graphs, then we use on-line coloring of interval filament graphs to obtain almost tight bounds on the chromatic number of subtree overlap graphs.

This is joint work with B. Walczak.

03.06
 Krzysztof Węsek
 O kolorowaniu płaszczyzny raz jeszcze

27.05
 Angelika Nicgorska-Miśkiewicz
 Liczba hydra grafu

20.05
 Przemysław Wenus
 Serdeczne kolorowanie hiperdrzew

13.05
 Joanna Sokół
 O kolorowaniach typu L(2,1) grafów przecięć dysków

06.05
 Konstanty Junosza-Szaniawski
 O kolorowaniu grafów przecięć dysków oraz cyrkularnym kolorowaniu płaszczyzny

29.04
 Jarosław Grytczuk
 Złożoność komunikacyjna

15.04
 Paweł Bilski (IM PAN)
 G-kolorowanie częściowych porządków

08.04
 Armin Fügenschuh (Helmut Schmidt University / University of the Federal Armed Forces Hamburg)
 Optimizing discrete and continuous problems over time

25.03
 Oskar Górniewicz
 Gry kooperacyjne na grafach

18.03
 Joanna Sokół
 The Total Action Lemma

11.03
 Jarosław Grytczuk
 Gra w czułe słówka

Streszczenie

29.01
 Rafał Górak
 Lokalizacja terminala telefonicznego w budynku. Wprowadzenie do problemu i dyskusja.

Podczas mojego krótkiego wystąpienia opowiem Państwu o zagadnieniach związanych
z wyznaczaniem lokalizacji telefonu wewnątrz budynku, na podstawie odczytu z wielu
sensorów. Problem jest o tyle ciekawy i trudny, że wewnątrz budynku nie jest dostępny
sygnał GPS. Badania nad tym problemem prowadzone są w ramach grantu NCBiR:
Kompleksowe metody wyznaczania lokalizacji terminala sieci telefonii komórkowej
przemieszczającego się w terenie otwartym i budynkach.
Mam nadzieję, że zachęcę Państwa do udziału w tym grancie, a podczas dyskusji uda
nam się wskazać ciekawe tematy badawcze, którymi moglibyście się zająć.

15.01
Czwartek, godz. 9:15, sala 216 (Gmach MiNI)
 Markus Reuther (Zuse Institut Berlin)
 A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem

14.01
 Markus Reuther (Zuse Institut Berlin)
 Local Search for the Resource Constrained Assignment Problem

12.01
Poniedziałek, godz. 10:15, sala 216 (Gmach MiNI)
  Urszula Pastwa
  Unikanie wzorców przez konika polnego

17.12
  Bartłomiej Bosek (Uniwersytet Jagielloński)
  Incremental algorithm on bipartite graphs
  
The talk presents the joint work of Bartłomiej Bosek, Darek Leniowski,
Piotr Sankowski, and Anna Zych. We investigated the problem of
maintaining maximum size matchings in incremental bipartite graphs. In
this problem, a bipartite graph G between n clients and n servers is
revealed online. The clients arrive in an arbitrary order and request
to be matched to a subset of servers. In our model we allow the
clients to switch between servers and want to maximize the matching
size between them, i.e. after a client arrives we find an augmenting
path from a client to a free server. Our goals in this model are
twofold. First, we want to minimize the number of times clients are
reallocated between the servers. Second, we want to give fast
algorithms that recompute such reallocation.
Literatura:
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.

10.12
   Paweł Naroski
   Uogólnienia dobrze znanych twierdzeń o pakowaniu grafów na przypadek hipergrafów jednorodnych

03.12
   Grzegorz Matecki (Uniwersytet Jagielloński)
   Leniwe skojarzenia w grafach dwudzielnych

26.11
   Konstanty Junosza-Szaniawski
   Kolorowanie typu L(p,q) grafów przecięć dysków
 
15.10
   Magda Dettlaff (Politechnika Gdańska)
   Liczba podziałowa dla dominowania w grafach
Powered by CMSimple