On the Diameter of the Pancake Network
From MaRDI portal
Publication:4366875
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
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
