Wyszukiwarka
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.
Autorzy (2)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
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 95 razy