اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديد(l,k)-Routing on Plane Grids
138
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(ell,k)$-routing problem, each node can send at most $ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $ell=k=1$. In the $r$-central routing problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$. In this article we study the permutation routing, the $r$-central routing and the general $(ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the emph{store-and-forward} $Delta$-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on $(ell,k)$-routing on plane grids. Our main contributions are the following: 1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. 2. Tight $r$-central routing algorithms on triangular and hexagonal grids. 3. Tight $(k,k)$-routing algorithms on square, triangular and hexagonal grids. 4. Good approximation algorithms (in terms of running time) for $(ell,k)$-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the $(ell,k)$-routing problem as a textsc{Weighted Edge Coloring} problem on bipartite graphs.
قيم البحث
اقرأ أيضاً
In 1997, Bousquet-Melou and Eriksson stated a broad generalization of Eulers distinct-odd partition theorem, namely the $(k,l)$-Euler theorem. Their identity involved the $(k,l)$-lecture-hall partitions, which, unlike usual difference conditions of p
artitions in Rogers-Ramanujan type identities, satisfy some ratio constraints. In a 2008 paper, in response to a question suggested by Richard Stanley, Savage and Yee provided a simple bijection for the $l$-lecture-hall partitions (the case $k=l$), whose specialization in $l=2$ corresponds to Sylvesters bijection. Subsequently, as an open question, a generalization of their bijection was suggested for the case $k,lgeq 2$. In the spirit of Savage and Yees work, we provide and prove in this paper slight variations of the suggested bijection, not only for the case $k,lgeq 2$ but also for the cases $(k,1)$ and $(1,k)$ with $kgeq 4$. Furthermore, we show that our bijections equal the recursive bijections given by Bousquet-Melou and Eriksson in their recursive proof of the $(k,l)$-lecture hall and finally provide the analogous recursive bijection for the $(k,l)$-Euler theorem.
A subset $A$ of the $k$-dimensional grid ${1,2, cdots, N}^k$ is called $k$-dimensional corner-free if it does not contain a set of points of the form ${ a } cup { a + de_i : 1 leq i leq k }$ for some $a in {1,2, cdots, N}^k$ and $d > 0$, where $e_1,e
_2, cdots, e_k$ is the standard basis of $mathbb{R}^k$. We define the maximum size of a $k$-dimensional corner-free subset of ${1,2, cdots, N}^k$ by $c_k(N)$. In this paper, we show that the number of $k$-dimensional corner-free subsets of the $k$-dimensional grid ${1,2, cdots, N}^k$ is at most $2^{O(c_k(N))}$ for infinitely many values of $N$. Our main tool for the proof is a supersaturation result for $k$-dimensional corners in sets of size $Theta(c_k(N))$ and the hypergraph container method.
The domination number of a graph $G = (V,E)$ is the minimum cardinality of any subset $S subset V$ such that every vertex in $V$ is in $S$ or adjacent to an element of $S$. Finding the domination numbers of $m$ by $n$ grids was an open problem for ne
arly 30 years and was finally solved in 2011 by Goncalves, Pinlou, Rao, and Thomasse. Many variants of domination number on graphs have been defined and studied, but exact values have not yet been obtained for grids. We will define a family of domination theories parameterized by pairs of positive integers $(t,r)$ where $1 leq r leq t$ which generalize domination and distance domination theories for graphs. We call these domination numbers the $(t,r)$ broadcast domination numbers. We give the exact values of $(t,r)$ broadcast domination numbers for small grids, and we identify upper bounds for the $(t,r)$ broadcast domination numbers for large grids and conjecture that these bounds are tight for sufficiently large grids.
In this paper we generalize permutations to plane permutations. We employ this framework to derive a combinatorial proof of a result of Zagier and Stanley, that enumerates the number of $n$-cycles $omega$, for which $omega(12cdots n)$ has exactly $k$
cycles. This quantity is $0$, if $n-k$ is odd and $frac{2C(n+1,k)}{n(n+1)}$, otherwise, where $C(n,k)$ is the unsigned Stirling number of the first kind. The proof is facilitated by a natural transposition action on plane permutations which gives rise to various recurrences. Furthermore we study several distance problems of permutations. It turns out that plane permutations allow to study transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Novel connections between these different distance problems are established via plane permutations.
Networks with a high degree of symmetry are useful models for parallel processor networks. In earlier papers, we defined several global communication tasks (universal exchange, universal broadcast, universal summation) that can be critical tasks when
complex algorithms are mapped to parallel machines. We showed that utilizing the symmetry can make network optimization a tractable problem. In particular, we showed that Cayley graphs have the desirable property that certain routing schemes starting from a single node can be transferred to all nodes in a way that does not introduce conflicts. In this paper, we define the concept of spanning factorizations and show that this property can also be used to transfer routing schemes from a single node to all other nodes. We show that all Cayley graphs and many (perhaps all) vertex transitive graphs have spanning factorizations.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
