APPROXIMATE BLOCK SORTING

DOI10.1142/S0129054106003863zbMath1093.68031OpenAlexW2027210027MaRDI QIDQ5291300

Venkatesh Raman, Raghavan Rama, Meena Mahajan, Suhas Vijaykumar

Publication date: 10 May 2006

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054106003863

zbMATH Keywords

approximation algorithmtranspositionsblock sortingblock merging

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (3)

Permutation-constrained common string partitions with applications ⋮ Block crossings in one-sided tanglegrams ⋮ A quadratic time 2-approximation algorithm for block sorting

Cites Work

• Bounds for sorting by prefix reversal
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Sorting by bounded block-moves
• Sorting by short block-moves
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Sorting Strings by Reversals and by Transpositions
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• Block Sorting is Hard
• Sorting a bridge hand
• Unnamed Item
• Unnamed Item

This page was built for publication: APPROXIMATE BLOCK SORTING