- Tytuł:
- Towards the boundary between easy and hard control problems in multicast Clos networks
- Autorzy:
-
Obszarski, P.
Jastrzębski, A.
Kubale, M. - Tematy:
-
Clos-network
2-cast call
hypergraph edge coloring
rearrageable network
nonblocking network
NP-completeness
3-uniform hypergraph
sieci
połączenie sieciowe
problem sieciowy - Pokaż więcej
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Powiązania:
- https://bibliotekanauki.pl/articles/200819.pdf Link otwiera się w nowym oknie
- Opis:
- In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially solvable instances as well as a number of NP-complete cases. Our results warn of possible troubles arising in the control of Clos networks even if they are composed of small-size switches in outer stages. This is in sharp contrast to classical unicast Clos networks for which all the control problems are polynomially solvable.
- Dostawca treści:
- Biblioteka Nauki
Artykuł