✦ LIBER ✦

k-k Routing, k-k Sorting, and Cut-Through Routing on the Mesh

✍ Scribed by S. Rajasekaran

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 1009 KB
Volume: 19
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1995.1042

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we present randomized algorithms for (k-k) routing, (k-k) sorting, and cut-through routing on an (n \times n) mesh connected computer (referred to simply as the mesh). The stated resource bounds hold with high probability. The algorithm for (k-k) routing runs in ((k / 2) n+o(k n)) steps. We also show that (k-k) sorting can be accomplished within ((k / 2) n+2 n+o(k n)) steps, and cut through routing can be done in (k n / 2+(3 / 2) n+o(k n)) steps. (k n / 2) is a known lower bound for all three problems (which is the bisection bound), and hence our algorithms are very nearly optimal. All the above-mentioned algorithms have optimal queue length. These algorithms also extend to higher-dimensional meshes. (8) 1995 Academic Press. Inc.

📜 SIMILAR VOLUMES

On the complexity of the k-customer vehi

On the complexity of the k-customer vehicle routing problem

✍ Refael Hassin; Shlomi Rubinstein 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 209 KB

k-Splittable delay constrained routing p

k-Splittable delay constrained routing problem: A branch-and-price approach

✍ Jérôme Truffot; Christophe Duhamel; Philippe Mahey 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB

On the mutual embeddability of (2k, k, k

On the mutual embeddability of (2k, k, k − 1) and (2k − 1, k, k) quasi-residual designs

✍ V.D Tonchev 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 307 KB

The shortest and the K-shortest routes a

The shortest and the K-shortest routes as assignment problems

✍ A. Weintraub 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 552 KB

## Abstract The problem of finding a shortest route in a network with unrestricted costs is approached through solving an assignment problem associated to the network. The upper bound on the number of elementary calculations required for the solution is 0(m^3^). However, in most cases, the actual

On the series Σk = 1∞(k2k)−1 k−n and rel

On the series Σk = 1∞(k2k)−1 k−n and related sums

✍ I.J Zucker 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 389 KB

On the Distributions δk and (δ')k

✍ E. L. Koh; Li Chen Kuan 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB

## Abstract Powers and products of distributions have not as yet been defined to hold true in general. In this paper, we choose a fixed δ‐sequence and use the concept of neutrix limit to give meaning to the distributions δ^__k__^ and (δ')^__k__^ for some __k__. These may be regarded as powers of Di