Routing equal-size messages on a slotted ring - Publication - Bridge of Knowledge

Search

Routing equal-size messages on a slotted ring

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

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 102 times

Recommended for you

Meta Tags