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)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C45: Eulerian and Hamiltonian graphs
Related Items
Statistical and Combinatorial Aspects of Comparative Genomics*, A sparse dynamic programming algorithm for alignment with non-overlapping inversions, An improved genetic algorithm for problem of genome rearrangement, A 14/11-approximation algorithm for sorting by short block-moves, Approximation algorithms for grooming in optical network design, Polynomial-time sortable stacks of burnt pancakes, The transposition median problem is NP-complete, Structural properties and tractability results for linear synteny, Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes, A more efficient algorithm for perfect sorting by reversals, Packing edge-disjoint cycles in graphs and the cyclomatic number, Sorting by bounded block-moves, \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions., Estimate the distance of genome rearrangements by reversals, Multiple genome rearrangement by swaps and by element duplications, A simpler and faster 1.5-approximation algorithm for sorting by transpositions, Predatory search algorithm with restriction of solution distance, COMPUTING SIGNED PERMUTATIONS OF POLYGONS, Edit Distances and Factorisations of Even Permutations