W czwartek, 7 grudnia 2017 o godz. 10:15 w sali 110 Instytutu Matematyki i Informatyki Uniwersytetu Opolskiego odbędzie się seminarium Zakładu Informatyki, na którym dr Zbigniew Lipiński wygłosi referat pt. „Algorytmy wyszukiwania drzew spinających o minimalnej wadze wierzchołka”.
Streszczenie:
Drzewa spinające o minimalnej wadze wierzchołka odgrywają ważną rolę w rozwiązywaniu zagadnień maksymalizacji czasu życia bezprzewodowych sieci ad-hoc dla transmisji broadcastowej. Bezprzewodową sieć można reprezentować jako skierowany graf w którym wierzchołkami są węzły sieci a krawędzie reprezentują połączenia komunikacyjne między węzłami. Dla regularnych sieci ad-hoc drzewa spinające o minimalnej wadze wierzchołka są rozwiązaniem zagadnienia maksymalizacji czasu życia sieci dla transmisji broadcastowej. Dla jednorodnych sieci ad-hoc rozwiązania tego zagadnienia można skonstruować pomocą tego typu drzew i algorytmów służących do równoważenia obciążenia węzłów. W referacie omówię trzy algorytmy wyszukiwania drzew spinających o minimalnej wadze wierzchołka. Pierwszy jest uogólnieniem algorytmu aproksymacyjnego Furera-Raghavacharianiego służącego do wyszukiwania drzew o minimalnym stopniu wierzchołka. Dwa pozostałe algorytmy wykorzystują przybliżone metody wyliczania wyznacznika ze zmodyfikowanej macierzy Laplace’a, która pełni rolę generatora drzew spinających.
Serdecznie zapraszamy.
