𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An optimal parallel algorithm for generating permutations in minimal change order

✍ Scribed by Jong-Chuang Tsay; Wei-Ping Lee

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
430 KB
Volume
20
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

Permutation generation is an important problem in combinatorial computing. In this paper we present an optimal parallel algorithm to generate all N! permutations of N objects. The algorithm is designed to be executed on a very simple computation model that is a linear array with N identical processors. Because of the simplicity and regularity of the processors, the model is very suitable for VLSI implementation. Another advantageous characteristic of this design is that it can generate all the permutations in minimal change order.

πŸ“œ SIMILAR VOLUMES

An Optimal Systolic Algorithm for Genera
An Optimal Systolic Algorithm for Generating Permutations in Lexicographic Order
✍ S.G. Akl; H. Meijer; I. Stojmenovic πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 693 KB

A systolic algorithm is described for generating all permutations of \(n\) elements in lexicographic order. The algorithm is designed to be executed on a linear array of \(n\) processors, each having constant size memory, and each being responsible for producing one element of a given permutation. T

An Optimal Shortest Path Parallel Algori
An Optimal Shortest Path Parallel Algorithm for Permutation Graphs
✍ O.H. Ibarra; Q. Zheng πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 512 KB

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in \(O(\log n)\) time using \(O(n / \log n)\) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be f

A Cost-Optimal Pipeline Algorithm for Pe
A Cost-Optimal Pipeline Algorithm for Permutation Generation in Lexicographic Order
✍ ClΓ©mentin Tayou Djamegni; Maurice TchuentΓ© πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 142 KB

In this paper we solve the open problem of designing a costoptimal parallel algorithm for generating permutations of M elements out of the set {0, 1, . . . , N -1}, in lexicographic order. Our algorithm runs on the simplest model of parallel computation, i.e., a linear array of size M, where each pr

An optimal EREW parallel algorithm for c
An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
✍ H.S. Chao; F.R. Hsu; R.C.T. Lee πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 498 KB

Given a undirected graph G, the breadth-first search tree is constructed by a breadth-first search on G. In this paper, an optimal parallel algorithm is presented for constructing the breadth-first search tree for permutation graphs in O(log n) time by using O(n/Iog n) processors under the EREW PRAM