A 4-approximation algorithm for k-prize collecting Steiner tree problems View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-03

AUTHORS

Yusa Matsuda, Satoshi Takahashi

ABSTRACT

This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems. More... »

PAGES

1-8

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s11590-018-1367-2

DOI

http://dx.doi.org/10.1007/s11590-018-1367-2

DIMENSIONS

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


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": "University of Electro-Communications", 
          "id": "https://www.grid.ac/institutes/grid.266298.1", 
          "name": [
            "The University of Electro-Communications, Chofu, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Matsuda", 
        "givenName": "Yusa", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Electro-Communications", 
          "id": "https://www.grid.ac/institutes/grid.266298.1", 
          "name": [
            "The University of Electro-Communications, Chofu, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Takahashi", 
        "givenName": "Satoshi", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1002/net.3230190602", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007863721"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.1997.1542", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019869761"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230240103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033094599"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060650", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044657663"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-005-0693-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048431055", 
          "https://doi.org/10.1007/s10107-005-0693-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/090771429", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062856700"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539793242618", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879797"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753979528826x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880045"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0895480194266331", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062882954"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11590-017-1135-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084032001", 
          "https://doi.org/10.1007/s11590-017-1135-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11590-017-1135-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084032001", 
          "https://doi.org/10.1007/s11590-017-1135-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11590-017-1135-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084032001", 
          "https://doi.org/10.1007/s11590-017-1135-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1996.548489", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095295328"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-03", 
    "datePublishedReg": "2019-03-01", 
    "description": "This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s11590-018-1367-2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.6142712", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.5853343", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.6162872", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1052645", 
        "issn": [
          "1862-4472", 
          "1862-4480"
        ], 
        "name": "Optimization Letters", 
        "type": "Periodical"
      }
    ], 
    "name": "A 4-approximation algorithm for k-prize collecting Steiner tree problems", 
    "pagination": "1-8", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f5aa3aebe754c7eda7938fa5c9c8ae6815b43063297a23ab15dd023d72744f59"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s11590-018-1367-2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110404032"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s11590-018-1367-2", 
      "https://app.dimensions.ai/details/publication/pub.1110404032"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T08:19", 
    "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/0000000282_0000000282/records_78272_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs11590-018-1367-2"
  }
]
 

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/s11590-018-1367-2'

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/s11590-018-1367-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11590-018-1367-2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11590-018-1367-2'


 

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

101 TRIPLES      21 PREDICATES      36 URIs      17 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s11590-018-1367-2 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N16f391eba3e84d6d88642c6115d20e28
4 schema:citation sg:pub.10.1007/s10107-005-0693-1
5 sg:pub.10.1007/s11590-017-1135-8
6 https://doi.org/10.1002/net.3230190602
7 https://doi.org/10.1002/net.3230240103
8 https://doi.org/10.1006/jcss.1997.1542
9 https://doi.org/10.1109/sfcs.1996.548489
10 https://doi.org/10.1137/090771429
11 https://doi.org/10.1137/s0097539793242618
12 https://doi.org/10.1137/s009753979528826x
13 https://doi.org/10.1137/s0895480194266331
14 https://doi.org/10.1145/1060590.1060650
15 schema:datePublished 2019-03
16 schema:datePublishedReg 2019-03-01
17 schema:description This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf sg:journal.1052645
22 schema:name A 4-approximation algorithm for k-prize collecting Steiner tree problems
23 schema:pagination 1-8
24 schema:productId N0a92c9daeb72453aad0ab50032863fdd
25 N448149ac2c3c47b98896f3c80fce6446
26 Na6c0a97b56ad4157889a4643c6fbe358
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110404032
28 https://doi.org/10.1007/s11590-018-1367-2
29 schema:sdDatePublished 2019-04-11T08:19
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher Neeef3e0bf5d742e2a991b31d19c7fd4e
32 schema:url https://link.springer.com/10.1007%2Fs11590-018-1367-2
33 sgo:license sg:explorer/license/
34 sgo:sdDataset articles
35 rdf:type schema:ScholarlyArticle
36 N0a92c9daeb72453aad0ab50032863fdd schema:name doi
37 schema:value 10.1007/s11590-018-1367-2
38 rdf:type schema:PropertyValue
39 N16f391eba3e84d6d88642c6115d20e28 rdf:first N7b129b76467742a3b4e6616655f05759
40 rdf:rest Na10daee314ed40ac8fd07092de9ff61b
41 N448149ac2c3c47b98896f3c80fce6446 schema:name readcube_id
42 schema:value f5aa3aebe754c7eda7938fa5c9c8ae6815b43063297a23ab15dd023d72744f59
43 rdf:type schema:PropertyValue
44 N69abc1834ba24c4382fc60202c5ab2d2 schema:affiliation https://www.grid.ac/institutes/grid.266298.1
45 schema:familyName Takahashi
46 schema:givenName Satoshi
47 rdf:type schema:Person
48 N7b129b76467742a3b4e6616655f05759 schema:affiliation https://www.grid.ac/institutes/grid.266298.1
49 schema:familyName Matsuda
50 schema:givenName Yusa
51 rdf:type schema:Person
52 Na10daee314ed40ac8fd07092de9ff61b rdf:first N69abc1834ba24c4382fc60202c5ab2d2
53 rdf:rest rdf:nil
54 Na6c0a97b56ad4157889a4643c6fbe358 schema:name dimensions_id
55 schema:value pub.1110404032
56 rdf:type schema:PropertyValue
57 Neeef3e0bf5d742e2a991b31d19c7fd4e schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
60 schema:name Information and Computing Sciences
61 rdf:type schema:DefinedTerm
62 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
63 schema:name Computation Theory and Mathematics
64 rdf:type schema:DefinedTerm
65 sg:grant.5853343 http://pending.schema.org/fundedItem sg:pub.10.1007/s11590-018-1367-2
66 rdf:type schema:MonetaryGrant
67 sg:grant.6142712 http://pending.schema.org/fundedItem sg:pub.10.1007/s11590-018-1367-2
68 rdf:type schema:MonetaryGrant
69 sg:grant.6162872 http://pending.schema.org/fundedItem sg:pub.10.1007/s11590-018-1367-2
70 rdf:type schema:MonetaryGrant
71 sg:journal.1052645 schema:issn 1862-4472
72 1862-4480
73 schema:name Optimization Letters
74 rdf:type schema:Periodical
75 sg:pub.10.1007/s10107-005-0693-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048431055
76 https://doi.org/10.1007/s10107-005-0693-1
77 rdf:type schema:CreativeWork
78 sg:pub.10.1007/s11590-017-1135-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084032001
79 https://doi.org/10.1007/s11590-017-1135-8
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1002/net.3230190602 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007863721
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1002/net.3230240103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033094599
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1006/jcss.1997.1542 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019869761
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1109/sfcs.1996.548489 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095295328
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1137/090771429 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856700
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1137/s0097539793242618 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879797
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1137/s009753979528826x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880045
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1137/s0895480194266331 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882954
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1145/1060590.1060650 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044657663
98 rdf:type schema:CreativeWork
99 https://www.grid.ac/institutes/grid.266298.1 schema:alternateName University of Electro-Communications
100 schema:name The University of Electro-Communications, Chofu, Japan
101 rdf:type schema:Organization
 




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


...