✦ LIBER ✦

Routing a Permutation in the Hypercube by Two Sets of Edge Disjoint Paths

✍ Scribed by Qian-Ping Gu; Hisao Tamaki

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 95 KB
Volume: 44
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.1997.1358

No coin nor oath required. For personal study only.

✦ Synopsis

Consider a hypercube regarded as a directed graph, with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths. This result implies that the hypercube can be made rearrangeable by virtually duplicating each edge through time-sharing (or through the use of two wavelengths in the case of optical connection), rather than by physically adding edges as in previous approaches. When our goal is to route as many source-destination pairs of the given permutation as possible by edge-disjoint paths, our result gives a 2-approximate solution which improves previous ones.

📜 SIMILAR VOLUMES

Hamiltonian cycles and paths with a pres

Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

✍ Rostislav Caha; V. Koubek 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result o

Volume 105, Number 1 (1994), in the arti

Volume 105, Number 1 (1994), in the article "Design of a Complete Set of Two-Dimensional Triple-Resonance Experiments for Assigning Labeled Proteins," by Bernhard Brutscher, Jean-Pierre Simorre, Michael S. Caffrey, and Dominique Marion, pages 77-82

📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 13 KB

Thoracic surgery. The surgical treatment

Thoracic surgery. The surgical treatment of thoracic diseases. By Howard Lilienthal M.D., F.A.C.S., Consulting Surgeon to Mount Sinai and Bellevue Hospitals; Professor of Clinical Surgery, Cornell University Medical College, etc. Two volumes. Royal 8vo. 1925. Pp. 1294 (with 904 illustrations, 13 in colours). Philadelphia and London: W. B. Saunders Co. 90s. net per set

📂 Article 📅 1926 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 2 views

Fractures and joint injuries. By Sir Reg

Fractures and joint injuries. By Sir Reginald Watson-Jones, B.Sc., M.Ch., Orth. F.R.C.S., F.R.A.C.S. (Hon.), F.A.C.S. (Hon.), Orthopædic Surgeon to His late Majesty King George VI; Director of Orthopédic and Accident Service, The London Hospital; etc. Fourth edition. 6⅝ × 9¾ in. In two volumes. Vol. I. Pp. 467 + xii, with 709 illustrations, many in colour. 1952. Edinburgh: E. & S. Livingstone. £ 6 per set

📂 Article 📅 1952 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 2 views