The Parameterized Complexity of the Shared Center Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Zhi-Zhong Chen , Lusheng Wang , Wenji Ma

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

PAGES

439-452

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31265-6_35

DOI

http://dx.doi.org/10.1007/978-3-642-31265-6_35

DIMENSIONS

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


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": "Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, 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 SAR", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
          ], 
          "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"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "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.", 
    "editor": [
      {
        "familyName": "K\u00e4rkk\u00e4inen", 
        "givenName": "Juha", 
        "type": "Person"
      }, 
      {
        "familyName": "Stoye", 
        "givenName": "Jens", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31265-6_35", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31264-9", 
        "978-3-642-31265-6"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "SC problem", 
      "center problem", 
      "parameterized complexity", 
      "polynomial-time approximation algorithm", 
      "mathematical model", 
      "minimization version", 
      "approximation algorithm", 
      "set of individuals", 
      "parameter D", 
      "algorithm", 
      "problem", 
      "complexity", 
      "NPs", 
      "database", 
      "set", 
      "input", 
      "radius", 
      "number of individuals", 
      "version", 
      "model", 
      "number", 
      "reference", 
      "individuals", 
      "status", 
      "haplotypes", 
      "paper"
    ], 
    "name": "The Parameterized Complexity of the Shared Center Problem", 
    "pagination": "439-452", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025688850"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31265-6_35"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31265-6_35", 
      "https://app.dimensions.ai/details/publication/pub.1025688850"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:49", 
    "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/chapter/chapter_360.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31265-6_35"
  }
]
 

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/978-3-642-31265-6_35'

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/978-3-642-31265-6_35'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31265-6_35'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31265-6_35'


 

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

108 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31265-6_35 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc5a275eb47b34e0b9244d27a94bc6200
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 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.
7 schema:editor N51f3bc070dba4508a0880657b48324a9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N1debf84f7e7e4e15982d7ae4dcce05f1
12 schema:keywords NPs
13 SC problem
14 algorithm
15 approximation algorithm
16 center problem
17 complexity
18 database
19 haplotypes
20 individuals
21 input
22 mathematical model
23 minimization version
24 model
25 number
26 number of individuals
27 paper
28 parameter D
29 parameterized complexity
30 polynomial-time approximation algorithm
31 problem
32 radius
33 reference
34 set
35 set of individuals
36 status
37 version
38 schema:name The Parameterized Complexity of the Shared Center Problem
39 schema:pagination 439-452
40 schema:productId Nbb22620f35a74bb69643e1bbfe177351
41 Nfbbd5e22920343d4b87189c81a7f299b
42 schema:publisher N1f913913373940749e2e38838df8c395
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025688850
44 https://doi.org/10.1007/978-3-642-31265-6_35
45 schema:sdDatePublished 2022-05-10T10:49
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N5a3120ea64114af48f8271e5ef00d62b
48 schema:url https://doi.org/10.1007/978-3-642-31265-6_35
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N1debf84f7e7e4e15982d7ae4dcce05f1 schema:isbn 978-3-642-31264-9
53 978-3-642-31265-6
54 schema:name Combinatorial Pattern Matching
55 rdf:type schema:Book
56 N1f913913373940749e2e38838df8c395 schema:name Springer Nature
57 rdf:type schema:Organisation
58 N346051d1700c448e82de2d13132f4e0f rdf:first N9ba046fa291d4b6b8148a5242dc58f06
59 rdf:rest rdf:nil
60 N51f3bc070dba4508a0880657b48324a9 rdf:first N6690c5205926420483cb7110a1ba787e
61 rdf:rest N346051d1700c448e82de2d13132f4e0f
62 N5a3120ea64114af48f8271e5ef00d62b schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N5b2dadf1b15e4875ba59a2a12a673389 rdf:first sg:person.01034033024.48
65 rdf:rest rdf:nil
66 N6690c5205926420483cb7110a1ba787e schema:familyName Kärkkäinen
67 schema:givenName Juha
68 rdf:type schema:Person
69 N9ba046fa291d4b6b8148a5242dc58f06 schema:familyName Stoye
70 schema:givenName Jens
71 rdf:type schema:Person
72 Nbb22620f35a74bb69643e1bbfe177351 schema:name doi
73 schema:value 10.1007/978-3-642-31265-6_35
74 rdf:type schema:PropertyValue
75 Nc5a275eb47b34e0b9244d27a94bc6200 rdf:first sg:person.015654265661.98
76 rdf:rest Nd73e6d393df04ba9aa3724961a3db295
77 Nd73e6d393df04ba9aa3724961a3db295 rdf:first sg:person.01105113721.52
78 rdf:rest N5b2dadf1b15e4875ba59a2a12a673389
79 Nfbbd5e22920343d4b87189c81a7f299b schema:name dimensions_id
80 schema:value pub.1025688850
81 rdf:type schema:PropertyValue
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.01034033024.48 schema:affiliation grid-institutes:None
89 schema:familyName Ma
90 schema:givenName Wenji
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034033024.48
92 rdf:type schema:Person
93 sg:person.01105113721.52 schema:affiliation grid-institutes:None
94 schema:familyName Wang
95 schema:givenName Lusheng
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
97 rdf:type schema:Person
98 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
99 schema:familyName Chen
100 schema:givenName Zhi-Zhong
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
102 rdf:type schema:Person
103 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
104 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
105 rdf:type schema:Organization
106 grid-institutes:grid.412773.4 schema:alternateName Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
107 schema:name Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
108 rdf:type schema:Organization
 




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


...