✦ LIBER ✦

Selection, Routing, and Sorting on the Star Graph

✍ Scribed by Sanguthevar Rajasekaran; David S.L. Wei

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 270 KB
Volume: 41
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.1996.1297

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problems of selection, routing, and sorting on an n-star graph (with n! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a "(k, 1, k) chain network") of the star graph which enables us to design efficient algorithms for the above mentioned problems. We present an algorithm that performs a sequence of n prefix computations in O(n 2 ) time. This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on the n-star graph in time O(n 3 ) and that selection of a set of uniformly distributed n keys can be performed in O(n 2 ) time with high probability. Finally, we also present a deterministic (nonoblivious) routing algorithm that realizes any permutation in O(n 3 ) steps on the n-star graph. There exists an algorithm in the literature that can perform a single prefix computation in O(n lg n) time. The best-known previous algorithm for sorting has a run time of O(n 3 lg n) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph.

📜 SIMILAR VOLUMES

k-k Routing, k-k Sorting, and Cut-Throug

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

✍ S. Rajasekaran 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 1009 KB

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

Routing permutations on a graph

✍ Mark Ramras 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 645 KB

Packet Routing and PRAM Emulation on Sta

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

✍ M.A. Palis; S. Rajasekaran 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 995 KB

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in \(O(\mathrm{D})\) ste

Embedding Meshes on the Star Graph

✍ S. Ranka; J.C. Wang; N. Yeh 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 362 KB

We develop algorithms for mapping \(n\)-dimensional meshes on a star graph of degree \(n\) with expansion 1 and dilation 3 . We show that an \(n\)-degree star graph can efficiently simulate an \(n\)-dimensional mesh. 1993 Academic Press, Inc.

On the spanning w-wide diameter of the s

On the spanning w-wide diameter of the star graph

✍ Cheng-Kuan Lin; Hua-Min Huang; D. Frank Hsu; Lih-Hsing Hsu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB

## Abstract Let __u__ and __v__ be any two distinct nodes of an undirected graph __G__, which is __k__‐connected. A container __C__(__u__,__v__) between __u__ and __v__ is a set of internally disjoint paths {__P__~1~,__P__~2~,…,__P__~__w__~} between __u__ and __v__ where 1 ≤ __w__ ≤ __k__. The widt

A Parallel Algorithm for Lagrange Interp

A Parallel Algorithm for Lagrange Interpolation on the Star Graph

✍ H. Sarbazi-Azad; M. Ould-Khaoua; L.M. Mackenzie; S.G. Akl 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 226 KB

This paper introduces a new parallel algorithm for computing an N(=n!)-point Lagrange interpolation on an n-star (n > 2). The proposed algorithm exploits several communication techniques on stars in a novel way, which can be adapted for computing similar functions. It is optimal and consists of thre