Search
Abstract
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).
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
JOURNAL OF SCHEDULING
no. T. 15,
pages 473 - 486,
ISSN: 1094-6136 - Language:
- English
- Publication year:
- 2012
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1007/s10951-011-0259-4
- Verified by:
- Gdańsk University of Technology
seen 59 times