Analizujemy problem routingu wiadomości w sieci slotted ring, biorąc pod uwagę dwa kryteria optymalizacyjne: długość uszeregowania oraz liczbę 'cykli' pracy sieci. Optymalny routing dla wiadomości o rozmiarze k jest silnie NP-trudny, natomiast dla k=q, gdzie q jest rozmiarem sieci, można obliczyć w czsie O(n^2log n) dla pierwszego kryterium. Podajemy również algorytm o czasie działania O(nlog n) oraz o stałym współczynniku dobroci. Dla drugiego kryterium, routing wiadomości o rozmiarze k, gdzie k dzieli q, jest silnie NP-trudny nawet dla ustalonego k>0, podczas gdy dla k=q optymalny routing może być obliczony w wielomianowym czasie O(nlog n).
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/s10951-011-0259-4
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2012
Źródło danych: MOSTWiedzy.pl - publikacja "Routing equal-size messages on a slotted ring" link otwiera się w nowej karcie
