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

Speaker(s)

Łukasz Kowalik

Affiliation

Uniwersytet Warszawski

Date

Oct. 6, 2005, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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).

---