Bounds for sorting by prefix reversal
From MaRDI portal
Publication:1253928
DOI10.1016/0012-365X(79)90068-2zbMath0397.68062WikidataQ55878414 ScholiaQ55878414MaRDI QIDQ1253928
William H. Gates, Christos H. Papadimitriou
Publication date: 1979
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items
Reliability analysis of the cactus-based networks ⋮ The spectral gap of graphs arising from substring reversals ⋮ Vulnerability analysis of multiprocessor system based on burnt pancake networks ⋮ Fault tolerant routing in the star and pancake interconnection networks ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals ⋮ APPROXIMATE BLOCK SORTING ⋮ Greedy flipping of pancakes and burnt pancakes ⋮ An \((18/11)n\) upper bound for sorting by prefix reversals ⋮ Data center interconnection networks are not hyperbolic ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model ⋮ Sorting by insertion of leading elements ⋮ On the problem of sorting burnt pancakes ⋮ Prefix and suffix reversals on strings ⋮ Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement ⋮ Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs ⋮ Iterative Deepening Dynamically Improved Bounds Bidirectional Search ⋮ Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups ⋮ How to sort by walking and swapping on paths and trees ⋮ Improved upper bound for sorting permutations by prefix transpositions ⋮ On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling ⋮ Flipping triangles and rectangles ⋮ Permutation patterns in genome rearrangement problems: the reversal model ⋮ Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs ⋮ Sorting balls and water: equivalence and computational complexity ⋮ Lengths of cycles in generalized pancake graphs ⋮ An Algorithm to Enumerate Grid Signed Permutation Classes ⋮ A quadratic lower bound for topswops ⋮ The generalized 3-connectivity of burnt pancake graphs and godan graphs ⋮ Physical zero-knowledge proof protocol for Topswops ⋮ Automorphism groups of the Pancake graphs ⋮ Cyclic Vertex (Edge) Connectivity of Burnt Pancake Graphs ⋮ Polynomial-time sortable stacks of burnt pancakes ⋮ On average and highest number of flips in pancake sorting ⋮ On the flip graphs on perfect matchings of complete graphs and signed reversal graphs ⋮ Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality ⋮ Flipping edge-labelled triangulations ⋮ Unnamed Item ⋮ Conditional fractional matching preclusion for burnt pancake graphs and pancake-like graphs (extended abstract) ⋮ Girth of pancake graphs ⋮ Small-diameter Cayley graphs for finite simple groups ⋮ The (conditional) matching preclusion for burnt pancake graphs ⋮ Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults ⋮ Edit Distances and Factorisations of Even Permutations ⋮ An algebraic view of bacterial genome evolution ⋮ 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 ⋮ Sorting permutations by block-interchanges ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Some problems on Cayley graphs ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ On Some Structural Properties of Star and Pancake Graphs ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ Cycles in the burnt pancake graph ⋮ Unnamed Item ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ 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 unified framework for off-line permutation routing in parallel networks ⋮ Sorting with fixed-length reversals ⋮ A quadratic time 2-approximation algorithm for block sorting ⋮ Ring embedding in faulty pancake graphs ⋮ Vertex reconstruction in Cayley graphs ⋮ Hypercube emulation of interconnection networks topologies ⋮ Bounding prefix transposition distance for strings and permutations ⋮ Fault-tolerant routing in burnt pancake graphs ⋮ On the global strong resilience of fault Hamiltonian graphs ⋮ A new general family of mixed graphs ⋮ Mutually independent Hamiltonian cycles for the pancake graphs and the star graphs ⋮ Relationship between extra edge connectivity and component edge connectivity for regular graphs ⋮ Fast Sequential and Parallel Vertex Relabelings of Km,m ⋮ A new algorithm for generation of permutations ⋮ Fault tolerance and diagnosability of burnt pancake networks under the comparison model ⋮ Parallel sorting on Cayley graphs ⋮ The generalized 4-connectivity of pancake graphs ⋮ A Hamilton cycle in the \(k\)-sided pancake network
Cites Work
