Strona główna > Archiwalny program seminarium > 2008/2009
2008/2009
2 X Sylwia Cichacz (AGH)
"Dowolne podziały grafów"
16 X Natalia Petryszyn
"Dekompozycja grafów na ścieżki o ograniczonej długości."
30 X Bartek Jabłoński
"Etykietowanie krawędzi automatów dające pokolorowanie synchroniczne."
Abstrakt: Zreferowana zostanie praca A.Trachtman'a dająca odpowiedz na około trzydziestoletnie pytanie: jakie są warunki konieczne i wystarczające na to, aby silnie spójny skierowany graf automatu posiadał kolorowanie synchroniczne. Inaczej mówiąc: jakie warunki musi spełniać graf automatu aby istniało dla niego kolorowanie pozwalające utworzyć słowo, które sprowadza wszystkie stany automatu w jeden. Omówiony zostanie również algorytm szukający słów resetujących.
6XI Bartek Jabłoński - kontynuacja
13 XI Zbigniew Lonc
"Dekompozycje grafów o wysokiej spójności na drogi"
20 XI Natalia Petryszyn
"Dekompozycje grafów o wysokiej spójności na drogi" cz. 2
4 XII Zbigniew Lonc
"Dekompozycje grafów o wysokiej spójności na drogi" cz.3
11 XII Dorota Kieszkowska
"Dowód tw. Dilwortha o kratach rozdzielnych"
18 XII Anna Zapart
"d-załamywalność i nerwy rodzin zbiorow wypuklych "
15 I Marta Przyborowska
"Nieekstremalne karty sąsiedztwa zbioru częściowo uporządkowanego"
24 II Kostek Szaniawski
"3-kolorowanie grafów planarnych bez trójkątów w czasie liniowym"
3 III Michał Tuczyński
"Zliczanie minimalnych transwersali w grafie"
24 III Paweł Naroski
"Ektremalne Grafy w Pewnym Twierdzeniu Sauera i Spencera o Pakowalności Grafów"
31 III Mirosław Kowaluk
"Problem najnizszego wspolnego przodka w acyklicznych grafach skierowanych."
Streszczenie: Najnizszym wspolnym przodkiem wierzcholkow u i v w acyklicznym grafie
skierowanym (dagu) jest ich przodek, ktory nie ma potomka bedacego przodkiem
wierzcholkow u i v.
Problem znajdywania najnizszego wspolnego przodka dla dowolnej pary
wierzcholkow dagu jest omawiany w literaturze juz od ponad trzydziestu
lat. Pierwszy asymptotycznie optymalny algorytm dla ukorzenionych drzew,
z liniowym czasem preprocessingu i stalym czasem odpowiedzi na zapytanie
o najnizszego wspolnego przodka zostal podany przez Harela i Tarjana w 1984
roku.
Jednak dopiero w 2001 zostala zlamana kubiczna bariera zlozonosci
preprocessingu, przy stalym czasie odpowiedzi na zapytanie, w przypadku
dowolnych grafow acyklicznych o n wierzcholkach i m krawedziach (Bender et al.
przedstawili algorytm o zlozonosci O(n^{2.688})). Od tego czasu wynik ten
zostal juz kilkakrotnie poprawiony.
W trakcie referatu zostanie przedstawiony optymalny algorytm znajdywania
najnizszych wspolnych przodkow w dagach rzadkich (zlozonosc O(nm))
oraz algorytmy wykorzystujace mnozenie macierzy boolowskich w celu otrzymania
szybkiego preprocessingu w przypadku dowolnych dagow (zlozonosc O(n^{2.575}))
oraz dagow, w ktorych kazda para wierzcholkow ma co najwyzej jednego
najnizszego wspolnego przodka (zlozonosc O(n^{2.376})). Naszkicowane zostana
rownieez rozwiazania niektorych mutacji omawianego problemu.
7 IV Anna Urbańska (UW)
"Kombinatoryczne algorytmy dla algebraicznych problemów związanych z macierzami."
21 IV Marta Przyborowska
"Szerokość posetu a jego rekonstrukcja"
28 IV Artur Giżycki
"Ciała uporządkowane w analizie niestandardowej"
12 V Natalia Petryszyn
"Rozkłady grafów na podgrafy dwóch rodzajów."
19 V Łukasz Rożej
"Rozgrywana liczba chromatyczna"
Przedstawiony będzie nowy wynik uogólniający twierdzenie o rozgrywanej liczbie chromatycznej dla kaktusów. Kaktusem nazywamy graf którego cykle są krawędziowo rozłączne.
26 V Kostek Szaniawski
"Zliczenie zbiorów niezależnych w grafach K_{1,3}-wolnych"
Przedstawiony zostanie algorytm zliczający zbiory niezależne (niekoniecznie maksymalne) w grafie K_{1,3}-wolnych o maksymalnym stopniu 3 działający w czasie O*(2^{n_3/6}). Algorytm działa w oparciu o pewne ciekawe własności wymienionych grafów.
2 VI Paweł Rzążewski
"Nieustanne pokrycie wierzchołkowe grafu"
- rozwinięcie problemu pokrycia wierzchołkowego: Ilu strażników potrzeba rozmieścić w wierzchołkach grafu by chronić go przed atakami na jego krawędzie? Po każdym ataku na krawędź strażnik znajdujący się w jej końcu musi ją naprawić przechodząc do drugiego jej końca. W referacie zostanie przedstawiony problem nieustannego pokrycia wierzchołkowego, dowód, że jest on co najmniej NP-zupełny. Zostanie też zaprezentowany algorytm 2-aproksymacyjny oraz rozwiązanie problemu dla drzew.
16VI Paweł Naroski
"Pakowanie grafów bez krótkich cykli"
23 VI Alex Rosa (McMaster University)
"Colouring combinatorial designs: recent advances and trends"