Temat: hypergraph edge coloring - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Towards the boundary between easy and hard control problems in multicast Clos networks
Autorzy:: Obszarski, P.
Jastrzębski, A.
Kubale, M.
Powiązania:: https://bibliotekanauki.pl/articles/200819.pdf
Data publikacji:: 2015
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: Clos-network
2-cast call
hypergraph edge coloring
rearrageable network
nonblocking network
NP-completeness
3-uniform hypergraph
sieci
połączenie sieciowe
problem sieciowy
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.
Źródło:: Bulletin of the Polish Academy of Sciences. Technical Sciences; 2015, 63, 3; 739-744
0239-7528
Pojawia się w:: Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Color-bounded hypergraphs, V: host graphs and subdivisions
Autorzy:: Bujtás, Csilla
Tuza, Zsolt
Voloshin, Vitaly
Powiązania:: https://bibliotekanauki.pl/articles/743863.pdf
Data publikacji:: 2011
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: mixed hypergraph
color-bounded hypergraph
vertex coloring
arboreal hypergraph
hypertree
feasible set
host graph
edge subdivision
Opis:: A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring.
We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀.
The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
Źródło:: Discussiones Mathematicae Graph Theory; 2011, 31, 2; 223-238
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "hypergraph edge coloring" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język