The Parameterized Complexity of the Shared Center Problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2012-12-20

AUTHORS

Zhi-Zhong Chen, Wenji Ma, Lusheng Wang

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. More... »

PAGES

269-293

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-012-9730-7

DOI

http://dx.doi.org/10.1007/s00453-012-9730-7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1011600604


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Division of Information System Design, Tokyo Denki University, Ishizaka, 359-0394, Hatoyama, Hiki, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Division of Information System Design, Tokyo Denki University, Ishizaka, 359-0394, Hatoyama, Hiki, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ma", 
        "givenName": "Wenji", 
        "id": "sg:person.01034033024.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034033024.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4612-0515-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050354225", 
          "https://doi.org/10.1007/978-1-4612-0515-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-10-115", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031267511", 
          "https://doi.org/10.1186/1471-2105-10-115"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39763-2_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011969846", 
          "https://doi.org/10.1007/978-3-540-39763-2_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02270-8_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004246225", 
          "https://doi.org/10.1007/978-3-642-02270-8_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-003-1028-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033688536", 
          "https://doi.org/10.1007/s00453-003-1028-3"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2012-12-20", 
    "datePublishedReg": "2012-12-20", 
    "description": "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.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-012-9730-7", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.6078852", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.7427614", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "69"
      }
    ], 
    "keywords": [
      "SC problem", 
      "center problem", 
      "parameterized complexity", 
      "polynomial-time approximation algorithm", 
      "mathematical model", 
      "minimization version", 
      "approximation algorithm", 
      "parameter D", 
      "set of individuals", 
      "algorithm", 
      "problem", 
      "complexity", 
      "NPs", 
      "database", 
      "set", 
      "radius", 
      "input", 
      "number of individuals", 
      "model", 
      "version", 
      "number", 
      "reference", 
      "analysis", 
      "individuals", 
      "status", 
      "haplotypes", 
      "paper"
    ], 
    "name": "The Parameterized Complexity of the Shared Center Problem", 
    "pagination": "269-293", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011600604"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-012-9730-7"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-012-9730-7", 
      "https://app.dimensions.ai/details/publication/pub.1011600604"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-10T10:06", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_557.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-012-9730-7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-012-9730-7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-012-9730-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-012-9730-7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-012-9730-7'


 

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      22 PREDICATES      57 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-012-9730-7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1a2a8e3ce06048038a643ada7459de5e
4 schema:citation sg:pub.10.1007/978-1-4612-0515-9
5 sg:pub.10.1007/978-3-540-39763-2_25
6 sg:pub.10.1007/978-3-642-02270-8_27
7 sg:pub.10.1007/s00453-003-1028-3
8 sg:pub.10.1186/1471-2105-10-115
9 schema:datePublished 2012-12-20
10 schema:datePublishedReg 2012-12-20
11 schema:description 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.
12 schema:genre article
13 schema:inLanguage en
14 schema:isAccessibleForFree true
15 schema:isPartOf Nb314d93e2f5749818b7816cdd73ec098
16 Nf661ccce09c2441ba28c677732ac05c7
17 sg:journal.1047644
18 schema:keywords NPs
19 SC problem
20 algorithm
21 analysis
22 approximation algorithm
23 center problem
24 complexity
25 database
26 haplotypes
27 individuals
28 input
29 mathematical model
30 minimization version
31 model
32 number
33 number of individuals
34 paper
35 parameter D
36 parameterized complexity
37 polynomial-time approximation algorithm
38 problem
39 radius
40 reference
41 set
42 set of individuals
43 status
44 version
45 schema:name The Parameterized Complexity of the Shared Center Problem
46 schema:pagination 269-293
47 schema:productId N57d06cbaaaea4993bf8363feb3d95764
48 N679eb3d6142d46f28f699b600a4e2920
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011600604
50 https://doi.org/10.1007/s00453-012-9730-7
51 schema:sdDatePublished 2022-05-10T10:06
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N3ba65da7c3024ea78320cd298faa56c1
54 schema:url https://doi.org/10.1007/s00453-012-9730-7
55 sgo:license sg:explorer/license/
56 sgo:sdDataset articles
57 rdf:type schema:ScholarlyArticle
58 N1a2a8e3ce06048038a643ada7459de5e rdf:first sg:person.015654265661.98
59 rdf:rest Nca03bc095be1490d994fc0971d28e805
60 N3ba65da7c3024ea78320cd298faa56c1 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N57d06cbaaaea4993bf8363feb3d95764 schema:name doi
63 schema:value 10.1007/s00453-012-9730-7
64 rdf:type schema:PropertyValue
65 N679eb3d6142d46f28f699b600a4e2920 schema:name dimensions_id
66 schema:value pub.1011600604
67 rdf:type schema:PropertyValue
68 N6ee7c5a4d0694313af4b061c63c03cca rdf:first sg:person.01105113721.52
69 rdf:rest rdf:nil
70 Nb314d93e2f5749818b7816cdd73ec098 schema:volumeNumber 69
71 rdf:type schema:PublicationVolume
72 Nca03bc095be1490d994fc0971d28e805 rdf:first sg:person.01034033024.48
73 rdf:rest N6ee7c5a4d0694313af4b061c63c03cca
74 Nf661ccce09c2441ba28c677732ac05c7 schema:issueNumber 2
75 rdf:type schema:PublicationIssue
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:grant.6078852 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-012-9730-7
83 rdf:type schema:MonetaryGrant
84 sg:grant.7427614 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-012-9730-7
85 rdf:type schema:MonetaryGrant
86 sg:journal.1047644 schema:issn 0178-4617
87 1432-0541
88 schema:name Algorithmica
89 schema:publisher Springer Nature
90 rdf:type schema:Periodical
91 sg:person.01034033024.48 schema:affiliation grid-institutes:grid.35030.35
92 schema:familyName Ma
93 schema:givenName Wenji
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034033024.48
95 rdf:type schema:Person
96 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
97 schema:familyName Wang
98 schema:givenName Lusheng
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
100 rdf:type schema:Person
101 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
102 schema:familyName Chen
103 schema:givenName Zhi-Zhong
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
105 rdf:type schema:Person
106 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
107 https://doi.org/10.1007/978-1-4612-0515-9
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-540-39763-2_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011969846
110 https://doi.org/10.1007/978-3-540-39763-2_25
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/978-3-642-02270-8_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004246225
113 https://doi.org/10.1007/978-3-642-02270-8_27
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/s00453-003-1028-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033688536
116 https://doi.org/10.1007/s00453-003-1028-3
117 rdf:type schema:CreativeWork
118 sg:pub.10.1186/1471-2105-10-115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031267511
119 https://doi.org/10.1186/1471-2105-10-115
120 rdf:type schema:CreativeWork
121 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
122 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
123 rdf:type schema:Organization
124 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Ishizaka, 359-0394, Hatoyama, Hiki, Saitama, Japan
125 schema:name Division of Information System Design, Tokyo Denki University, Ishizaka, 359-0394, Hatoyama, Hiki, Saitama, Japan
126 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...