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.

Witryna, którą obecnie przeglądasz, wykorzystuje pliki cookies w celu poprawnej realizacji dostarczanych usług i informacji oraz w celach gromadzenia anonimowych informacji statystycznych. Więcej informacji >>

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close