Routing equal-size messages on a slotted ring - Publikacja - MOST Wiedzy

Wyszukiwarka

Routing equal-size messages on a slotted ring

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 56 razy

Publikacje, które mogą cię zainteresować

Meta Tagi