@inbook {IOPORT.06101503,
    author       = {Zhang, Chihao and Jiang, Haitao and Zhu, Binhai},
    title        = {Radiation hybrid map construction problem parameterized.},
    year         = {2012},
    booktitle    = {Combinatorial optimization and applications. 6th international conference, COCOA 2012, Banff, AB, Canada, August 5--9, 2012. Proceedings},
    isbn         = {978-3-642-31769-9},
    pages        = {127-137},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-31770-5_12},
    abstract     = {Summary: We study the radiation hybrid map construction (RHMC) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be NP-complete even when all gene clusters are of size two and the corresponding problem (RHMC$_{2})$ admits efficient constant-factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three (RHMC $_{3})$. Let $p$-RHMC be a parameterized version of RHMC where the parameter is the size of solution. We present a linear kernel for $p$-RHMC$_{3}$ of size $22k$, together with a bounded search tree algorithm, we obtain an FPT algorithm running in $O(6^{k} k + n)$ time. For $p$-RHMC $_{2}$ we present a bounded search tree algorithm which runs in $O^{*}(2.45^{k})$ time, greatly improving the previous bound using weak kernels.},
    identifier   = {06101503},
}