Konferencja SODA; "Mierz i zwyciężaj": metoda analizy algorytmów wykładniczych.

Speaker(s)

Łukasz Kowalik

Affiliation

Uniwersytet Warszawski

Date

Oct. 12, 2006, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Seminarium będzie się składało z dwóch części. Podczas części pierwszej krótko przedstawię najciekawsze wyniki z tegorocznej konferencji SODA. Nieco bardziej szczegółowo opowiem o pracy Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, "Measure and Conquer: A Simple O(2^0.288n) Independent Set Algorithm", która zawiera interesującą koncepcję (nazywną szumnie "mierz i zwyciężaj") analizowania złożoności czasowej algorytmów wykładniczych typu "branch-and-reduce". Podczas drugiej części przestawię własną pracę wykorzystującą m.in. metodę "mierz i zwyciężaj". Mój algorytm dotyczy 3-kolorowania krawędziowego grafów (dowolnych) i poprawia wcześniejszy algorytm autorstwa Beigela i Eppsteina, który działa w czasie O(2^(n/2)) Uwaga! Po seminarium planujemy wznowić stary zwyczaj swobodniejszej dyskusji przy kawie i ciastkach.

---