Sorting signed permutations by reversals, revisited

DOI10.1016/j.jcss.2004.12.002zbMath1068.68051OpenAlexW2048727187MaRDI QIDQ1775771

Haim Kaplan, Elad Verbin

Publication date: 4 May 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.12.002

zbMATH Keywords

Parallel algorithmsRandom algorithmsGenome rearrangementsSorting by reversals

Mathematics Subject Classification ID

Searching and sorting (68P10) Biochemistry, molecular biology (92C40) Parallel algorithms in computer science (68W10) Genetics and epigenetics (92D10) Randomized algorithms (68W20)

Related Items (1)

An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A data structure useful for finding Hamiltonian cycles
• Parallel general prefix computations with geometric, algebraic, and other applications
• Transforming cabbage into turnip
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals
• Priority Search Trees
• Self-adjusting binary search trees
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• TIME-OPTIMAL ALGORITHMS FOR GENERALIZED DOMINANCE COMPUTATION AND RELATED PROBLEMS ON MESH CONNECTED COMPUTERS AND MESHES WITH MULTIPLE BROADCASTING
• Data Structures for Traveling Salesmen
• Genome Rearrangements and Sorting by Reversals
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Combinatorial Pattern Matching
• Parallelism in random access machines
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS

This page was built for publication: Sorting signed permutations by reversals, revisited