On the Diameter of the Pancake Network

DOI10.1006/jagm.1997.0874zbMath0888.68007DBLPjournals/jal/HeydariS97OpenAlexW2025402252WikidataQ56287387 ScholiaQ56287387MaRDI QIDQ4366875

Mohammad Heydari, Ivan Hal Sudborough

Publication date: 1 June 1998

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1997.0874

zbMATH Keywords

pancake problempancake network

Mathematics Subject Classification ID

Searching and sorting (68P10) Mathematical problems of computer architecture (68M07) Computer system organization (68M99)

Related Items (34)

The spectral gap of graphs arising from substring reversals ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals ⋮ Greedy flipping of pancakes and burnt pancakes ⋮ An \((18/11)n\) upper bound for sorting by prefix reversals ⋮ Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model ⋮ Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups ⋮ On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling ⋮ A quadratic lower bound for topswops ⋮ Physical zero-knowledge proof protocol for Topswops ⋮ Automorphism groups of the Pancake graphs ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ On average and highest number of flips in pancake sorting ⋮ Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality ⋮ Block Sorting is Hard ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Pancake flipping and sorting permutations ⋮ Short proofs for cut-and-paste sorting of permutations ⋮ Pancake flipping is hard ⋮ Some problems on Cayley graphs ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ On Some Structural Properties of Star and Pancake Graphs ⋮ Cycles in the burnt pancake graph ⋮ The super connectivity of the pancake graphs and the super laceability of the star graphs ⋮ Some relations on prefix reversal generators of the symmetric and hyperoctahedral group ⋮ A quadratic time 2-approximation algorithm for block sorting ⋮ Ring embedding in faulty pancake graphs ⋮ Vertex reconstruction in Cayley graphs ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ Survey on path and cycle embedding in some networks ⋮ A new general family of mixed graphs ⋮ Mutually independent Hamiltonian cycles for the pancake graphs and the star graphs ⋮ A Hamilton cycle in the \(k\)-sided pancake network

This page was built for publication: On the Diameter of the Pancake Network