Cykl Hamiltona w grafach nieskierowanych szybciej niz 2^n.

Speaker(s)

Łukasz Kowalik

Affiliation

Uniwersytet Warszawski

Date

Dec. 9, 2010, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Problemy cyklu Hamiltona i TSP to jedne z najintensywniej badanych problemow optymalizacyjnych. W latach 60-tych Held i Karp podali prosty algorytm oparty na programowaniu dynamicznym, wymagajacy czasu O*(2^n) i pamieci O(2^n). Powstalo naturalne pytanie, czy te granice da sie przekroczyc. Szybko okazalo sie ze w przypadku cyklu Hamiltona, ktory jest problemem odrobine prostszym mozna uzyskac mala poprawe: za pomoca zasady wlaczen i wylaczen uzyskuje sie pamiec wielomianowa bez pogorszenia czasu dzialania. I ten stan rzeczy utrzymywal sie przez niemal... 50 lat. Dopiero w tym roku Andreas Bjorklund wykazal, ze problem cyklu Hamiltona w grafach nieskierowanych mozna rozwiazac w czasie O*(2^{3/4n}).

Podczas referatu opowiem ze szczegolami algorytm dla przypadku grafow dwudzielnych, ktory jest dosc prosty i dziala w czasie O*(2^{n/2}) = O(1.42^n). Nastepnie naszkicuje jak ten algorytm rozszerza sie do przypadku ogolnego.

---