Cykl Hamiltona w grafach nieskierowanych szybciej niz 2^n.

Prelegent(ci)

Łukasz Kowalik

Afiliacja

Uniwersytet Warszawski

Termin

9 grudnia 2010 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---