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

approximation algorithmmaximum independent setgenome rearrangementbreakpoint graphsorting by reversalsalternating cycle decomposition\(k\)-set packing

Mathematics Subject Classification ID

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

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

(9)

• 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
• Erratum: ``The approximability of the exemplar breakpoint distance problem
• An approximation algorithm for sorting by reversals and transpositions
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
• 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?

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)