𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Routing Permutations on Graphs via Factors

✍ Scribed by Dominique Barth; Petrişor Panaite

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
826 KB
Volume
54
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On diameter of permutation graphs
On diameter of permutation graphs
✍ Gu, Weizhen 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Let G be a connected graph with n vertices. Let a be a permutation in S n . The a-generalized graph over G, denoted by P a (G), consists of two disjoint, identical copies of G along with edges £a(£). In this paper, we investigated the relation between diameter of P a (G) and diameter of G for any pe

Routing Permutations on Hypercube Machin
Routing Permutations on Hypercube Machines with Half-Duplex Links
✍ C.S. Raghavendra; M.A. Sridhar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 466 KB

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given t

Deterministic Permutation Routing on Mes
Deterministic Permutation Routing on Meshes
✍ Jop F. Sibeyn; Bogdan S. Chlebus; Michael Kaufmann 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 248 KB

New deterministic algorithms for routing permutations on two-dimensional meshes are developed. On an n = n array, one algorithm runs in the optimal 2 и n y 2 steps, with maximum queue length 32. Another algorithm runs in near-Ž . optimal time, 2 и n q O O 1 steps, with a maximum queue length of only

On testing isomorphism of permutation gr
On testing isomorphism of permutation graphs
✍ Charles J. Colbourn 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 530 KB

## Abstract A polynomial time algorithm for testing isomorphism of permutation graphs (comparability graphs of 2‐dimensional partial orders) is described. It operates by performing two types of simplifying transformations on the graph; the contraction of duplicate vertices and the contraction of un