Search
Abstract
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.
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Title of issue:
- Proceedings of the 2nd International Conference on Information Technology, ICIT 2010 28-30 June 2010, Gdansk, Poland strony 0 - 0
- Language:
- English
- Publication year:
- 2010
- Bibliographic description:
- 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
- Verified by:
- Gdańsk University of Technology
seen 60 times