Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?

DOI10.1007/978-3-319-39817-4_20MaRDI QIDQ4632186zbMATH OpenOpenAlexFDO

Authors Lianrong Pu, Haitao Jiang

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-39817-4_20

zbMATH Keywords

breakpoint graphcycle decompositiongenome rearrangement

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10)

Recommendations

• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Improved approximation for breakpoint graph decomposition and sorting by reversals
• scientific article; zbMATH DE number 2073943
• A further improved approximation algorithm for breakpoint graph decomposition
• The distribution of cycles in breakpoint graphs of signed permutations

Cites work

• A further improved approximation algorithm for breakpoint graph decomposition
• scientific article; zbMATH DE number 1263193 (Why is no real title available?)
• scientific article; zbMATH DE number 910919 (Why is no real title available?)
• On the tightness of the alternating-cycle lower bound for sorting by reversals
• The Approximability of the Exemplar Breakpoint Distance Problem

Cited in

(3)

• A 1.375-approximation algorithm for unsigned translocation sorting
• The distribution of cycles in breakpoint graphs of signed permutations
• Can a breakpoint graph be decomposed into none other than 2-cycles?

This page was built for publication: Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?

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