✦ LIBER ✦

On the Diameter of the Pancake Network

✍ Scribed by Mohammad H. Heydari; I.Hal Sudborough

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 310 KB
Volume: 25
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0874

No coin nor oath required. For personal study only.

✦ Synopsis

The n-dimensional pancake network, P , has processors labeled with each of the n n! distinct permutations of length n and a connection between two processors when the label of one is obtained from the other by some prefix reversal. Each permutation is considered as a stack of different size pancakes. The well known Ž . pancake problem concerns the number, f n , of prefix reversals required to sort n pancakes.

Ž . We describe a 9r8 n q 2 step sorting sequence for Gates and Papadimitriou's stack of n pancakes, , used for establishing their lower bound, thus disproving n

📜 SIMILAR VOLUMES

On the complexity of the pancake problem

✍ Fuxiang Yu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

The complexity of designing a network wi

The complexity of designing a network with minimum diameter

✍ J. Plesnik 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB

On the diameters of the stars

✍ E. A. Kreiken 📂 Article 📅 1936 🏛 John Wiley and Sons 🌐 English ⚖ 433 KB 👁 2 views

Researches on the Diameter of Venus

✍ T. J. J. See 📂 Article 📅 1900 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

Researches on the diameter of jupiter

✍ T. J. J. See 📂 Article 📅 1901 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 2 views

Researches on the Diameter of Mercury

✍ T. J. J. See 📂 Article 📅 1901 🏛 John Wiley and Sons 🌐 English ⚖ 541 KB