Sorting Permutations by Reversals and Eulerian Cycle Decompositions
From MaRDI portal
Publication:4255810
DOI10.1137/S089548019731994XzbMath0916.68074MaRDI QIDQ4255810
Publication date: 27 June 1999
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Related Items (45)
Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ Approximation algorithms for sorting permutations by length-weighted short rearrangements ⋮ Permutation-constrained common string partitions with applications ⋮ Exploiting pseudo-locality of interchange distance ⋮ Estimate the distance of genome rearrangements by reversals ⋮ A new approach for the reversal distance with indels and moves in intergenic regions ⋮ Structural properties and tractability results for linear synteny ⋮ On the average number of reversals needed to sort signed permutations ⋮ Sorting by prefix block-interchanges ⋮ Sorting genomes by prefix double-cut-and-joins ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations ⋮ Polynomial-time sortable stacks of burnt pancakes ⋮ The transposition median problem is NP-complete ⋮ Unnamed Item ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Edit Distances and Factorisations of Even Permutations ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ COMPUTING SIGNED PERMUTATIONS OF POLYGONS ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ A more efficient algorithm for perfect sorting by reversals ⋮ Packing edge-disjoint cycles in graphs and the cyclomatic number ⋮ Maximum cycle packing in Eulerian graphs using local traces ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ Packing Euler graphs with traces ⋮ Approximation algorithms for grooming in optical network design ⋮ A simpler and faster 1.5-approximation algorithm for sorting by transpositions ⋮ On the hardness of maximum rank aggregation problems ⋮ Statistical and Combinatorial Aspects of Comparative Genomics* ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ Predatory search algorithm with restriction of solution distance ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ Sorting a permutation by best short swaps ⋮ Reversal distance on genomes with different gene content and intergenic regions information ⋮ Weighted Minimum-Length Rearrangement Scenarios. ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Sorting by bounded block-moves ⋮ An improved genetic algorithm for problem of genome rearrangement ⋮ Unnamed Item ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
This page was built for publication: Sorting Permutations by Reversals and Eulerian Cycle Decompositions
