Sorting permutations by block-interchanges
From MaRDI portal
Publication:673336
DOI10.1016/S0020-0190(96)00155-XzbMath0900.68232OpenAlexW2004163905MaRDI QIDQ673336
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(96)00155-x
Related Items
A topological framework for signed permutations ⋮ Sorting by multi-cut rearrangements ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ Permutation-constrained common string partitions with applications ⋮ Exploiting pseudo-locality of interchange distance ⋮ Sorting by \(k\)-cuts on signed permutations ⋮ A versatile combinatorial approach of studying products of long cycles in symmetric groups ⋮ Sorting by Cuts, Joins and Whole Chromosome Duplications ⋮ On the average number of reversals needed to sort signed permutations ⋮ Sorting by prefix block-interchanges ⋮ On the relationship between histogram indexing and block-mass indexing ⋮ Sorting permutations: Games, genomes, and cycles ⋮ Approximate String Matching with Address Bit Errors ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ Unnamed Item ⋮ The distribution of cycles in breakpoint graphs of signed permutations ⋮ Pattern matching with address errors: rearrangement distances ⋮ Edit Distances and Factorisations of Even Permutations ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ Sorting by Transpositions Is Difficult ⋮ Approximate string matching with stuck address bits ⋮ The average number of block interchanges needed to sort a permutation and a recent result of Stanley ⋮ Measures for the exceptionality of gene order in conserved genomic regions ⋮ An improved algorithm for sorting by block-interchanges based on permutation groups ⋮ \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges ⋮ On the effective and automatic enumeration of polynomial permutation classes ⋮ Interchange rearrangement: the element-cost model ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ On the computational complexity of closest genome problems ⋮ Quantifying CDS sortability of permutations by strategic pile size ⋮ Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations ⋮ Approximate string matching with address bit errors ⋮ The Emperor Has No Caps! A Comparison of DCJ and Algebraic Distances ⋮ The role of colour flows in matrix element computations and Monte Carlo simulations ⋮ Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach ⋮ Approximation algorithms for sorting by \(k\)-cuts on signed permutations
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of finding minimum-length generator sequences
- Sorting by insertion of leading elements
- Bounds for sorting by prefix reversal
- Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
- The minimum-length generator sequence problem is NP-hard
- Genome Rearrangements and Sorting by Reversals
