A further improved approximation algorithm for breakpoint graph decomposition

DOI10.1023/B:JOCO.0000031419.12290.2bzbMath1088.68182OpenAlexW2014859375MaRDI QIDQ1768609

Tao Jiang, Guo-Hui 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 algorithmgenome rearrangementmaximum independent setbreakpoint graphsorting by reversalsalternating cycle decomposition\(k\)-set packing

Mathematics Subject Classification ID

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

Related Items

On sorting unsigned permutations by double-cut-and-joins, Can a breakpoint graph be decomposed into none other than 2-cycles?, A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations, Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?, An approximation algorithm for sorting by reversals and transpositions