Disjoint Segments with Maximum Density View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Yen Hung Chen , Hsueh-I Lu , Chuan Yi Tang

ABSTRACT

Given a sequence A of numbers and two positive integers ℓ and k, we study the problem to find k disjoint segments of A, each has length at least ℓ, such that their sum of densities is maximized. We give the first known polynomial-time algorithm for the problem: For general k, our algorithm runs in O(n ℓk) time. For the special case with k = 2 (respectively, k = 3), we also show how to solve the problem in O(n) (respectively, O(n + ℓ2)) time. More... »

PAGES

845-850

References to SciGraph publications

Book

TITLE

Computational Science – ICCS 2005

ISBN

978-3-540-26043-1
978-3-540-32114-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11428848_108

DOI

http://dx.doi.org/10.1007/11428848_108

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, 300, Hsinchu, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Yen Hung", 
        "id": "sg:person.01347725471.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Taiwan University", 
          "id": "https://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, 300, Hsinchu, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Chuan Yi", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.jcss.2004.08.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000816720"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/19.1.151", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010842492"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/27.19.3899", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016985300"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(92)90216-i", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020432276"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(87)90689-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022754921"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.052410099", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023462148"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00010-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026217820"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00010-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026217820"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02459499", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030934869", 
          "https://doi.org/10.1007/bf02459499"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02459499", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030934869", 
          "https://doi.org/10.1007/bf02459499"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0168-9525(00)02024-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035021159"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230120410", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046499939"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0888-7543(92)90024-m", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046950562"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0020-0190(03)00225-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050333918"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0020-0190(03)00225-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050333918"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45089-0_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051758054", 
          "https://doi.org/10.1007/3-540-45089-0_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45089-0_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051758054", 
          "https://doi.org/10.1007/3-540-45089-0_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/cmb.2004.11.766", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059245292"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/10.3.219", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059413371"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1101/gr.10.12.1986", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060407385"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539704440430", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879515"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511790492", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098676015"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Given a sequence A of numbers and two positive integers \u2113 and k, we study the problem to find k disjoint segments of A, each has length at least \u2113, such that their sum of densities is maximized. We give the first known polynomial-time algorithm for the problem: For general k, our algorithm runs in O(n \u2113k) time. For the special case with k = 2 (respectively, k = 3), we also show how to solve the problem in O(n) (respectively, O(n + \u21132)) time.", 
    "editor": [
      {
        "familyName": "Sunderam", 
        "givenName": "Vaidy S.", 
        "type": "Person"
      }, 
      {
        "familyName": "van Albada", 
        "givenName": "Geert Dick", 
        "type": "Person"
      }, 
      {
        "familyName": "Sloot", 
        "givenName": "Peter M. A.", 
        "type": "Person"
      }, 
      {
        "familyName": "Dongarra", 
        "givenName": "Jack J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11428848_108", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-26043-1", 
        "978-3-540-32114-9"
      ], 
      "name": "Computational Science \u2013 ICCS 2005", 
      "type": "Book"
    }, 
    "name": "Disjoint Segments with Maximum Density", 
    "pagination": "845-850", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009122253"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11428848_108"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2b75d2c4ab187b2d7ab3249765f40a26a05b56ecb8f1b079200f41037a7e5ee9"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11428848_108", 
      "https://app.dimensions.ai/details/publication/pub.1009122253"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29194_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11428848_108"
  }
]
 

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/11428848_108'

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/11428848_108'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11428848_108'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11428848_108'


 

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

153 TRIPLES      23 PREDICATES      45 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11428848_108 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N16abed3f909542c6a1012d3fe49a0fa2
4 schema:citation sg:pub.10.1007/3-540-45089-0_23
5 sg:pub.10.1007/bf02459499
6 https://doi.org/10.1002/net.3230120410
7 https://doi.org/10.1016/0020-0190(92)90216-i
8 https://doi.org/10.1016/0022-2836(87)90689-9
9 https://doi.org/10.1016/0888-7543(92)90024-m
10 https://doi.org/10.1016/j.jcss.2004.08.001
11 https://doi.org/10.1016/s0020-0190(03)00225-4
12 https://doi.org/10.1016/s0022-0000(02)00010-7
13 https://doi.org/10.1016/s0168-9525(00)02024-2
14 https://doi.org/10.1017/cbo9780511790492
15 https://doi.org/10.1073/pnas.052410099
16 https://doi.org/10.1089/cmb.2004.11.766
17 https://doi.org/10.1093/bioinformatics/10.3.219
18 https://doi.org/10.1093/bioinformatics/19.1.151
19 https://doi.org/10.1093/nar/27.19.3899
20 https://doi.org/10.1101/gr.10.12.1986
21 https://doi.org/10.1137/s0097539704440430
22 schema:datePublished 2005
23 schema:datePublishedReg 2005-01-01
24 schema:description Given a sequence A of numbers and two positive integers ℓ and k, we study the problem to find k disjoint segments of A, each has length at least ℓ, such that their sum of densities is maximized. We give the first known polynomial-time algorithm for the problem: For general k, our algorithm runs in O(n ℓk) time. For the special case with k = 2 (respectively, k = 3), we also show how to solve the problem in O(n) (respectively, O(n + ℓ2)) time.
25 schema:editor Nb4052131991c4c8eb034ad0a085d5112
26 schema:genre chapter
27 schema:inLanguage en
28 schema:isAccessibleForFree true
29 schema:isPartOf Nbebb61aa2df1492bae9deefa353b4cb1
30 schema:name Disjoint Segments with Maximum Density
31 schema:pagination 845-850
32 schema:productId N9a17e8acf7aa45d4a3b67f4bb65da35a
33 Nc76d7672594e46deb4a67b98713f5627
34 Neae2fa0dfd0e4225ae1839e718196e88
35 schema:publisher Ndd5ae7c3c5c6429a892c57d5f9c3dbe2
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009122253
37 https://doi.org/10.1007/11428848_108
38 schema:sdDatePublished 2019-04-16T08:01
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher N58287e7efd09420d9d36bc4aaa807a77
41 schema:url https://link.springer.com/10.1007%2F11428848_108
42 sgo:license sg:explorer/license/
43 sgo:sdDataset chapters
44 rdf:type schema:Chapter
45 N16abed3f909542c6a1012d3fe49a0fa2 rdf:first sg:person.01347725471.75
46 rdf:rest Ncbfe22427a5f463eba6ed224fbf406f3
47 N186a50d51d2644d99d3c883e2672347c schema:familyName Dongarra
48 schema:givenName Jack J.
49 rdf:type schema:Person
50 N58287e7efd09420d9d36bc4aaa807a77 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N5d22f88508d649b5a26a041d3d9aac29 rdf:first sg:person.01312526135.27
53 rdf:rest rdf:nil
54 N7af53d5d37cc4803809dda80f43e8f80 schema:familyName van Albada
55 schema:givenName Geert Dick
56 rdf:type schema:Person
57 N87919ee108274bc082e3b114dce4bfd7 rdf:first N186a50d51d2644d99d3c883e2672347c
58 rdf:rest rdf:nil
59 N91146ae1f4a44b5d8b8ae7c822617cf0 rdf:first N7af53d5d37cc4803809dda80f43e8f80
60 rdf:rest Na79bfb444d094f529d6f14a885b829b0
61 N97d4d773b5f0430d9970a051f4c36005 schema:familyName Sloot
62 schema:givenName Peter M. A.
63 rdf:type schema:Person
64 N9a17e8acf7aa45d4a3b67f4bb65da35a schema:name doi
65 schema:value 10.1007/11428848_108
66 rdf:type schema:PropertyValue
67 Na79bfb444d094f529d6f14a885b829b0 rdf:first N97d4d773b5f0430d9970a051f4c36005
68 rdf:rest N87919ee108274bc082e3b114dce4bfd7
69 Nb4052131991c4c8eb034ad0a085d5112 rdf:first Ncb1aceae256342b68108f7dc7a047515
70 rdf:rest N91146ae1f4a44b5d8b8ae7c822617cf0
71 Nbebb61aa2df1492bae9deefa353b4cb1 schema:isbn 978-3-540-26043-1
72 978-3-540-32114-9
73 schema:name Computational Science – ICCS 2005
74 rdf:type schema:Book
75 Nc76d7672594e46deb4a67b98713f5627 schema:name dimensions_id
76 schema:value pub.1009122253
77 rdf:type schema:PropertyValue
78 Ncb1aceae256342b68108f7dc7a047515 schema:familyName Sunderam
79 schema:givenName Vaidy S.
80 rdf:type schema:Person
81 Ncbfe22427a5f463eba6ed224fbf406f3 rdf:first sg:person.013345515575.46
82 rdf:rest N5d22f88508d649b5a26a041d3d9aac29
83 Ndd5ae7c3c5c6429a892c57d5f9c3dbe2 schema:location Berlin, Heidelberg
84 schema:name Springer Berlin Heidelberg
85 rdf:type schema:Organisation
86 Neae2fa0dfd0e4225ae1839e718196e88 schema:name readcube_id
87 schema:value 2b75d2c4ab187b2d7ab3249765f40a26a05b56ecb8f1b079200f41037a7e5ee9
88 rdf:type schema:PropertyValue
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
93 schema:name Computation Theory and Mathematics
94 rdf:type schema:DefinedTerm
95 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
96 schema:familyName Tang
97 schema:givenName Chuan Yi
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
99 rdf:type schema:Person
100 sg:person.013345515575.46 schema:affiliation https://www.grid.ac/institutes/grid.19188.39
101 schema:familyName Lu
102 schema:givenName Hsueh-I
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
104 rdf:type schema:Person
105 sg:person.01347725471.75 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
106 schema:familyName Chen
107 schema:givenName Yen Hung
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75
109 rdf:type schema:Person
110 sg:pub.10.1007/3-540-45089-0_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051758054
111 https://doi.org/10.1007/3-540-45089-0_23
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/bf02459499 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030934869
114 https://doi.org/10.1007/bf02459499
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1002/net.3230120410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046499939
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/0020-0190(92)90216-i schema:sameAs https://app.dimensions.ai/details/publication/pub.1020432276
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1016/0022-2836(87)90689-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022754921
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1016/0888-7543(92)90024-m schema:sameAs https://app.dimensions.ai/details/publication/pub.1046950562
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1016/j.jcss.2004.08.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000816720
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1016/s0020-0190(03)00225-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050333918
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1016/s0022-0000(02)00010-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026217820
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1016/s0168-9525(00)02024-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035021159
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1017/cbo9780511790492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098676015
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1073/pnas.052410099 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023462148
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1089/cmb.2004.11.766 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059245292
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1093/bioinformatics/10.3.219 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059413371
139 rdf:type schema:CreativeWork
140 https://doi.org/10.1093/bioinformatics/19.1.151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010842492
141 rdf:type schema:CreativeWork
142 https://doi.org/10.1093/nar/27.19.3899 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016985300
143 rdf:type schema:CreativeWork
144 https://doi.org/10.1101/gr.10.12.1986 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060407385
145 rdf:type schema:CreativeWork
146 https://doi.org/10.1137/s0097539704440430 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879515
147 rdf:type schema:CreativeWork
148 https://www.grid.ac/institutes/grid.19188.39 schema:alternateName National Taiwan University
149 schema:name Department of Computer Science and Information Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C.
150 rdf:type schema:Organization
151 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
152 schema:name Department of Computer Science, National Tsing Hua University, 300, Hsinchu, Taiwan, R.O.C.
153 rdf:type schema:Organization
 




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


...