标题：Can a breakpoint graph be decomposed into none other than 2-cycles?
作者：Pu, Lianrong; Lin, Yu; Zhu, Daming; Jiang, Haitao
作者机构：[Pu, Lianrong; Zhu, Daming; Jiang, Haitao] Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.; [Lin, Yu] Australian Natl Univ, 更多
通讯作者：Jiang, HT;Jiang, Haitao
通讯作者地址：[Jiang, HT]Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.
来源：THEORETICAL COMPUTER SCIENCE
关键词：Algorithm; Complexity; Breakpoint graph; Genome rearrangement; Cycle; decomposition
摘要：Breakpoint graph has been widely used as a key data structure in algorithm design for genome rearrangements. The problem of breakpoint graph cycle decomposition, which asks for a largest collection of edge-disjoint cycles, is crucial in computing rearrangement distances between genomes. This problem is NP-hard, and can be approximated to 1.4193+epsilon. It is still open for deciding whether a breakpoint graph can admit a cycle decomposition with none other than 2-cycles. In this paper, we present a linear time algorithm to detect whether a breakpoint graph can be decomposed into none other than 2-cycles. (C) 2017 Elsevier B.V. All rights reserved.