A further improved approximation algorithm for breakpoint graph decomposition

DOI10.1023/B:JOCO.0000031419.12290.2BMaRDI QIDQ1768609zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Guohui Lin

Publication date 15 March 2005

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

Full work available at URL https://doi.org/10.1023/b:joco.0000031419.12290.2b

zbMATH Keywords

\(k\)-set packingalternating cycle decompositionapproximation algorithmbreakpoint graphgenome rearrangementmaximum independent setsorting by reversals

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Protein sequences, DNA sequences (92D20)

Recommendations

• Improved approximation for breakpoint graph decomposition and sorting by reversals
• Approximation algorithms for the median problem in the breakpoint model
• scientific article; zbMATH DE number 1947393
• scientific article; zbMATH DE number 2073943
• An approximation algorithm for sorting by reversals and transpositions

Cited in

(10)

• An approximation algorithm for sorting by reversals and transpositions
• Improved approximation for breakpoint graph decomposition and sorting by reversals
• On sorting unsigned permutations by double-cut-and-joins
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Erratum: ``The approximability of the exemplar breakpoint distance problem
• Revisiting the minimum breakpoint linearization problem
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Additive Bounding, Worst-Case Analysis, and the Breakpoint Median Problem
• Maximum alternating clean balanced cycle decomposition and applications in rearrangement distance problems
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations

This page was built for publication: A further improved approximation algorithm for breakpoint graph decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1768609)