Listowe kolorowanie krawędziowe grafów i aproksymacja lesistości grafu

Prelegent(ci)

Łukasz Kowalik

Afiliacja

Uniwersytet Warszawski

Termin

6 października 2005 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Postaram się krótko przedstawić problem listowego kolorowania krawędziowego grafów oraz opowiedzieć o znanych wynikach w tej dziedzinie. Szczególnie uważnie będę się przyglądał grafom planarnym. Z listowym kolorowaniem krawędziowym grafów ogólnych i planarnych wiąże się kilka bardzo ciekawych problemów otwartych -- przede wszystkim teoriografowych, ale również algorytmicznych. Lesistość (ang. arboricity) grafu to najczęściej stosowana miara rzadkości/gęstości grafu. Problem mierzenia lesistości jest wielomianowy, ale najlepsze znane algorytmy opieraja sie metodach przeplywowych i mają złożoność rzedu O~(m^3/2). Jeśli starczy czasu drugą część seminarium poświęcę na zreferowanie efektywnych algorytmow aproksymacyjnych dla problemu mierzenia lesistosci oraz pokrewnego problemu znajdowania optymalnej orientacji grafu. Tu takze opisze kilka otwartych problemów (myślę że dużo prostszych niż te związane z kolorowaniem listowym).

---