Radiation hybrid map construction problem parameterized

Chihao Zhang (), Haitao Jiang () and Binhai Zhu ()
Additional contact information
Chihao Zhang: Shanghai Jiao Tong University
Haitao Jiang: Shandong University
Binhai Zhu: Montana State University

Journal of Combinatorial Optimization, 2014, vol. 27, issue 1, No 2, 3-13

Abstract: Abstract In this paper, we study the Radiation hybrid map construction ( $$\mathsf{{RHMC} }$$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $$\mathsf{{NP} }$$ -complete even when all gene clusters are of size two and the corresponding problem ( $$\mathsf{{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 ( $$\mathsf{{RHMC}_3 }$$ ). Let $${p\text{- }\mathsf {RHMC} }$$ be a parameterized version of $$\mathsf{{RHMC} }$$ where the parameter is the size of solution. We present a linear kernel for $${p\text{- }\mathsf {RHMC}_3 }$$ of size $$22k$$ that when combined with a bounded search-tree algorithm, gives an FPT algorithm running in $$O(6^kk+n)$$ time. For $${p\text{- }\mathsf {RHMC}_3 }$$ we present a bounded search tree algorithm which runs in $$O^*(2.45^k)$$ time, greatly improving the previous bound using weak kernels.

Keywords: Radiation hybrid mapping; Kernel; Fixed-parameter tractable (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9608-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:1:d:10.1007_s10878-013-9608-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9608-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().