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).
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1007/s10951-011-0259-4
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2012
Source: MOSTWiedzy.pl - publication "Routing equal-size messages on a slotted ring" link open in new tab
