Improved approximation for breakpoint graph decomposition and sorting by reversals

DOI10.1023/A:1013851611274zbMath0993.05113OpenAlexW1557322746MaRDI QIDQ1598878

Romeo Rizzi, Alberto Caprara

Publication date: 28 May 2002

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1013851611274

zbMATH Keywords

stable setset packingapproximation algorithmsbreakpoint graphsorting by reversalsalternating cycle decomposition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (3)

On sorting unsigned permutations by double-cut-and-joins ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations ⋮ An approximation algorithm for sorting by reversals and transpositions

This page was built for publication: Improved approximation for breakpoint graph decomposition and sorting by reversals