The complexity of finding minimum-length generator sequences
From MaRDI portal
Publication:1058290
DOI10.1016/0304-3975(85)90047-7zbMath0564.68031OpenAlexW2028889910MaRDI QIDQ1058290
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90047-7
Related Items
Hash functions and Cayley graphs ⋮ Approximation algorithms for sorting permutations by length-weighted short rearrangements ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Computing short generator sequences ⋮ Swapping Colored Tokens on Graphs ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation ⋮ Exploiting pseudo-locality of interchange distance ⋮ Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement ⋮ A review of metrics on permutations for search landscape analysis ⋮ How to sort by walking and swapping on paths and trees ⋮ Bisection width of transposition graphs ⋮ Sorting by prefix block-interchanges ⋮ Token Swapping on Trees ⋮ Hypercube embeddings and Cayley graphs generated by transpositions ⋮ An algebraic model for inversion and deletion in bacterial genome rearrangement ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ Particle computation: complexity, algorithms, and logic ⋮ Reconfiguration and enumeration of optimal cyclic ladder lotteries ⋮ Finding Antimagic Labelings of Trees by Evolutionary Search ⋮ Cyclic group blocking polyhedra ⋮ Unnamed Item ⋮ The Time Complexity of the Token Swapping Problem and Its Parallel Variants ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ Edit Distances and Factorisations of Even Permutations ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ Cyclic shift problems on graphs ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ Sorting permutations by block-interchanges ⋮ Growth in SL2 over finite fields ⋮ Swapping colored tokens on graphs ⋮ Diameter bounds and recursive properties of Full-Flag Johnson graphs ⋮ Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ Unnamed Item ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ Sorting with fixed-length reversals ⋮ Sorting a permutation by best short swaps ⋮ Cryptographic Hash Functions and Expander Graphs: The End of the Story? ⋮ Exact upper bound for sorting Rn with LE ⋮ Sorting by bounded block-moves ⋮ Swapping labeled tokens on graphs ⋮ On the Strictness of a Bound for the Diameter of Cayley Graphs Generated by Transposition Trees ⋮ Task swapping networks in distributed systems
Cites Work
