New Approximation Algorithms for the Steiner Tree Problems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-03

AUTHORS

Marek Karpinski, Alexander Zelikovsky

ABSTRACT

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively. More... »

PAGES

47-65

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1009758919736

DOI

http://dx.doi.org/10.1023/a:1009758919736

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "International Computer Science Institute, Berkeley, California, Email", 
          "id": "http://www.grid.ac/institutes/grid.185107.a", 
          "name": [
            "Department of Computer Science, University of Bonn, 53117, Bonn, and", 
            "International Computer Science Institute, Berkeley, California, Email"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Thornton Hall, University of Virginia, 22903-2442, Email, VA", 
          "id": "http://www.grid.ac/institutes/grid.27755.32", 
          "name": [
            "Department of Computer Science, Thornton Hall, University of Virginia, 22903-2442, Email, VA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zelikovsky", 
        "givenName": "Alexander", 
        "id": "sg:person.01121041073.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-57568-5_285", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007399294", 
          "https://doi.org/10.1007/3-540-57568-5_285"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01187035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025618982", 
          "https://doi.org/10.1007/bf01187035"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997-03", 
    "datePublishedReg": "1997-03-01", 
    "description": "The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively.", 
    "genre": "article", 
    "id": "sg:pub.10.1023/a:1009758919736", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "keywords": [
      "Steiner tree problem", 
      "new approximation algorithm", 
      "approximation algorithm", 
      "tree problem", 
      "metric spaces", 
      "optimal solution", 
      "arbitrary metric", 
      "approximation ratio", 
      "Steiner points", 
      "terminal point", 
      "possible deviations", 
      "rectilinear plane", 
      "problem", 
      "algorithm", 
      "space", 
      "point", 
      "solution", 
      "dependence", 
      "plane", 
      "set", 
      "metrics", 
      "novel technique", 
      "deviation", 
      "technique", 
      "shortest trees", 
      "trees", 
      "ratio"
    ], 
    "name": "New Approximation Algorithms for the Steiner Tree Problems", 
    "pagination": "47-65", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004234523"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1009758919736"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1009758919736", 
      "https://app.dimensions.ai/details/publication/pub.1004234523"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-12-01T06:21", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_295.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1023/a:1009758919736"
  }
]
 

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.1023/a:1009758919736'

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.1023/a:1009758919736'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1009758919736'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1009758919736'


 

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

107 TRIPLES      21 PREDICATES      55 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1009758919736 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 anzsrc-for:0103
4 schema:author N973da7d2b62843a0a8bdae74de04ef22
5 schema:citation sg:pub.10.1007/3-540-57568-5_285
6 sg:pub.10.1007/bf01187035
7 schema:datePublished 1997-03
8 schema:datePublishedReg 1997-03-01
9 schema:description The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively.
10 schema:genre article
11 schema:isAccessibleForFree false
12 schema:isPartOf N5ddc0703fd8b41d3b5b35cd833237e6c
13 Ne21f4e1009c243ecb0b3ff5a9fa1128b
14 sg:journal.1036683
15 schema:keywords Steiner points
16 Steiner tree problem
17 algorithm
18 approximation algorithm
19 approximation ratio
20 arbitrary metric
21 dependence
22 deviation
23 metric spaces
24 metrics
25 new approximation algorithm
26 novel technique
27 optimal solution
28 plane
29 point
30 possible deviations
31 problem
32 ratio
33 rectilinear plane
34 set
35 shortest trees
36 solution
37 space
38 technique
39 terminal point
40 tree problem
41 trees
42 schema:name New Approximation Algorithms for the Steiner Tree Problems
43 schema:pagination 47-65
44 schema:productId Nc1370e2337c648efb73b4d31a22b052a
45 Ne8c8873780af430d8c1c83cc7f76be35
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004234523
47 https://doi.org/10.1023/a:1009758919736
48 schema:sdDatePublished 2022-12-01T06:21
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Nbae6795895ef45218d2428029542a22a
51 schema:url https://doi.org/10.1023/a:1009758919736
52 sgo:license sg:explorer/license/
53 sgo:sdDataset articles
54 rdf:type schema:ScholarlyArticle
55 N5ddc0703fd8b41d3b5b35cd833237e6c schema:volumeNumber 1
56 rdf:type schema:PublicationVolume
57 N973da7d2b62843a0a8bdae74de04ef22 rdf:first sg:person.011636042271.02
58 rdf:rest Nf0f046c832db4a4c9fe9870ccfbbc546
59 Nbae6795895ef45218d2428029542a22a schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Nc1370e2337c648efb73b4d31a22b052a schema:name doi
62 schema:value 10.1023/a:1009758919736
63 rdf:type schema:PropertyValue
64 Ne21f4e1009c243ecb0b3ff5a9fa1128b schema:issueNumber 1
65 rdf:type schema:PublicationIssue
66 Ne8c8873780af430d8c1c83cc7f76be35 schema:name dimensions_id
67 schema:value pub.1004234523
68 rdf:type schema:PropertyValue
69 Nf0f046c832db4a4c9fe9870ccfbbc546 rdf:first sg:person.01121041073.51
70 rdf:rest rdf:nil
71 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
72 schema:name Mathematical Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
75 schema:name Applied Mathematics
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
78 schema:name Numerical and Computational Mathematics
79 rdf:type schema:DefinedTerm
80 sg:journal.1036683 schema:issn 1382-6905
81 1573-2886
82 schema:name Journal of Combinatorial Optimization
83 schema:publisher Springer Nature
84 rdf:type schema:Periodical
85 sg:person.01121041073.51 schema:affiliation grid-institutes:grid.27755.32
86 schema:familyName Zelikovsky
87 schema:givenName Alexander
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
89 rdf:type schema:Person
90 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.185107.a
91 schema:familyName Karpinski
92 schema:givenName Marek
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
94 rdf:type schema:Person
95 sg:pub.10.1007/3-540-57568-5_285 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007399294
96 https://doi.org/10.1007/3-540-57568-5_285
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/bf01187035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025618982
99 https://doi.org/10.1007/bf01187035
100 rdf:type schema:CreativeWork
101 grid-institutes:grid.185107.a schema:alternateName International Computer Science Institute, Berkeley, California, Email
102 schema:name Department of Computer Science, University of Bonn, 53117, Bonn, and
103 International Computer Science Institute, Berkeley, California, Email
104 rdf:type schema:Organization
105 grid-institutes:grid.27755.32 schema:alternateName Department of Computer Science, Thornton Hall, University of Virginia, 22903-2442, Email, VA
106 schema:name Department of Computer Science, Thornton Hall, University of Virginia, 22903-2442, Email, VA
107 rdf:type schema:Organization
 




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


...