\input zb-basic
\input zb-ioport
\iteman{io-port 06101503}
\itemau{Zhang, Chihao; Jiang, Haitao; Zhu, Binhai}
\itemti{Radiation hybrid map construction problem parameterized.}
\itemso{Lin, Guohui (ed.), Combinatorial optimization and applications. 6th international conference, COCOA 2012, Banff, AB, Canada, August 5--9, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31769-9/pbk). Lecture Notes in Computer Science 7402, 127-137 (2012).}
\itemab
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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-31770-5\_12}
\end