A randomized FPT approximation algorithm for maximum alternating-cycle decomposition with applications

DOI10.1007/978-3-319-94776-1_3MaRDI QIDQ1790950zbMATH OpenOpenAlexFDO

Authors Haitao Jiang, Lianrong Pu, Letu Qingge, David Sankoff, Binhai Zhu

Publication date 4 October 2018

Full work available at URL https://doi.org/10.1007/978-3-319-94776-1_3

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27) Genetics and epigenetics (92D10)

Recommendations

• A (1.408+ )-approximation algorithm for sorting unsigned genomes by reciprocal translocations
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
• A linear time approximation algorithm for the DCJ distance for genomes with bounded number of duplicates
• An approximation algorithm for sorting by reversals and transpositions
• On sorting unsigned permutations by double-cut-and-joins

Cited in

(3)

• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Exact and approximation algorithms for computing optimal fat decompositions
• A randomized FPT approximation algorithm for sorting unsigned genomes by translocations: breaking the 1.375 approximation barrier

This page was built for publication: A randomized FPT approximation algorithm for maximum alternating-cycle decomposition with applications

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