The parameterized complexity of the shared center problem

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

2 Scopus Citations
Scopus Metrics
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)269-293
Journal / PublicationAlgorithmica
Volume69
Issue number2
Publication statusPublished - Jun 2014

Link(s)

DOI

DOI
Check@CityULib
Link to Scopus https://www.scopus.com/record/display.uri?eid=2-s2.0-84897548592&origin=recordpage
Permanent Link https://scholars.cityu.edu.hk/en/publications/publication(4d3f21fb-846e-40ee-bdfc-1a2df1f898db).html

Abstract

Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem and apply them to linkage analysis. © 2012 Springer Science+Business Media New York.

Research Area(s)

  • Allele-sharing status, Haplotype inference, Linkage analysis, Parameterized algorithms, Parameterized complexity, Pedigree

Fingerprint

Publication fingerprints text

100
Algorithm Mathematics
100
Parameterized Compl... Keyphrases
100
Center Problem Keyphrases
100
algorithms INIS
100
Complexity Computer Science
50
Number Mathematics
50
Complete Mathematics
50
Polynomial Time Mathematics
50
Database Mathematics
50
Mathematical Modeli... Mathematics
Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]
The parameterized complexity of the shared center problem. / Chen, Zhi-Zhong; Ma, Wenji; Wang, Lusheng.
In: Algorithmica, Vol. 69, No. 2, 06.2014, p. 269-293.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review