Wyszukiwarka
Abstrakt
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).
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF SCHEDULING
nr T. 15,
strony 473 - 486,
ISSN: 1094-6136 - Język:
- angielski
- Rok wydania:
- 2012
- Opis bibliograficzny:
- Dereniowski D., Kubiak W.: Routing equal-size messages on a slotted ring // JOURNAL OF SCHEDULING. -Vol. T. 15, nr. nr 4 (2012), s.473-486
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10951-011-0259-4
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 102 razy