Can a breakpoint graph be decomposed into none other than 2-cycles?

DOI10.1016/j.tcs.2017.09.019zbMath1393.68047OpenAlexW2762979389MaRDI QIDQ2636497

Daming Zhu, Lianrong Pu, Haitao Jiang, Yu Lin

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.019

zbMATH Keywords

complexityalgorithmgenome rearrangementcycle decompositionbreakpoint graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Data structures (68P05)

Related Items (1)

A 1.375-approximation algorithm for unsigned translocation sorting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of unsigned translocation distance
• A new linear time algorithm to compute the genomic distance via the double cut and join distance
• On the tightness of the alternating-cycle lower bound for sorting by reversals
• A further improved approximation algorithm for breakpoint graph decomposition
• A 1.75-approximation algorithm for unsigned translocation distance
• Genome Rearrangements and Sorting by Reversals
• The Approximability of the Exemplar Breakpoint Distance Problem
• Polynomial-time algorithm for computing translocation distance between genomes

This page was built for publication: Can a breakpoint graph be decomposed into none other than 2-cycles?