Rearrangeability in multicast Clos networks is NP-complete - Publikacja - MOST Wiedzy

Wyszukiwarka

Rearrangeability in multicast Clos networks is NP-complete

Abstrakt

Przestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite graph then connecting paths are easy transformed into edge coloring. It is also natural to use on-line edge coloring algorithms. However, the things get more complicated in case of multicast connections. There are four models of multicast 3-stage elos networks: model-l where only the first stage switches do not have fan-out capability, model-2 where only the second stage switches do not have fan-out capability, model-3 where only the third stage switches do not have fan-out capability and model-O where no switches lack fanout capability. In the paper we show some new results on model o and model-l multicast elos networks. In particular, we focus on rearrangeable multicast networks and prove that the problem of their rearranging is NP-complete.

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
Proceedings of the 2nd International Conference on Information Technology, ICIT 2010  28-30 June 2010, Gdansk, Poland strony 0 - 0
Język:
angielski
Rok wydania:
2010
Opis bibliograficzny:
Jastrzębski A., Kubale M.: Rearrangeability in multicast Clos networks is NP-complete// Proceedings of the 2nd International Conference on Information Technology, ICIT 2010  28-30 June 2010, Gdansk, Poland/ ed. eds. Alicja Konczakowska, Lech Hasse. Gdańsk: , 2010, s.0-0
Weryfikacja:
Politechnika Gdańska

wyświetlono 18 razy

Publikacje, które mogą cię zainteresować

Meta Tagi