1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Piotr Berman , Marek Karpinski , Alexander Zelikovsky

ABSTRACT

Given a connected graph G = (V,E) with nonnegative costs on edges, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c:E\rightarrow {\mathcal R}^+$\end{document}, and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279. More... »

PAGES

86-97

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03367-4_8

DOI

http://dx.doi.org/10.1007/978-3-642-03367-4_8

DIMENSIONS

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


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 Computer Science & Engineering, Pennsylvania State University, University Park, 16802, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science & Engineering, Pennsylvania State University, University Park, 16802, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn, 53117, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn, 53117, Bonn, Germany"
          ], 
          "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, Georgia State University, 30303, Atlanta, GA, USA", 
          "id": "http://www.grid.ac/institutes/grid.256304.6", 
          "name": [
            "Department of Computer Science, Georgia State University, 30303, Atlanta, GA, USA"
          ], 
          "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"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Given a connected graph G\u2009=\u2009(V,E) with nonnegative costs on edges, \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$c:E\\rightarrow {\\mathcal R}^+$\\end{document}, and a subset of terminal nodes R\u2009\u2282\u2009V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Gavrilova", 
        "givenName": "Marina", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "T\u00f3th", 
        "givenName": "Csaba D.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03367-4_8", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03366-7", 
        "978-3-642-03367-4"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "distance 1", 
      "Steiner tree problem", 
      "tree problem", 
      "minimum cost subgraph", 
      "good approximation", 
      "approximation algorithm", 
      "connected graph G", 
      "graph G", 
      "nonnegative costs", 
      "general problem", 
      "MAX SNP", 
      "problem", 
      "subset", 
      "node r", 
      "approximation", 
      "algorithm", 
      "subgraphs", 
      "long time", 
      "SNPs", 
      "R.", 
      "time", 
      "ratio", 
      "edge", 
      "cost"
    ], 
    "name": "1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2", 
    "pagination": "86-97", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026258834"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03367-4_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03367-4_8", 
      "https://app.dimensions.ai/details/publication/pub.1026258834"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:19", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_369.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03367-4_8"
  }
]
 

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-03367-4_8'

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-03367-4_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03367-4_8'

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-03367-4_8'


 

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

118 TRIPLES      22 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03367-4_8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfc85fed6dca245e7a278a00a03141a2e
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description Given a connected graph G = (V,E) with nonnegative costs on edges, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c:E\rightarrow {\mathcal R}^+$\end{document}, and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.
7 schema:editor N6a5f6dd042d047cfa8ac278dd5bac895
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Ne84505945afd45d8bce85c86c8192dba
11 schema:keywords MAX SNP
12 R.
13 SNPs
14 Steiner tree problem
15 algorithm
16 approximation
17 approximation algorithm
18 connected graph G
19 cost
20 distance 1
21 edge
22 general problem
23 good approximation
24 graph G
25 long time
26 minimum cost subgraph
27 node r
28 nonnegative costs
29 problem
30 ratio
31 subgraphs
32 subset
33 time
34 tree problem
35 schema:name 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
36 schema:pagination 86-97
37 schema:productId N4baa664dc571431e805d35a0e02bbd4a
38 N6c35dabeed8b435db3ac939fd1ca801d
39 schema:publisher N0d3b9490d9754914a153f42914d7f0e5
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026258834
41 https://doi.org/10.1007/978-3-642-03367-4_8
42 schema:sdDatePublished 2022-08-04T17:19
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N8a14838048234c358917f3b7a52b24cf
45 schema:url https://doi.org/10.1007/978-3-642-03367-4_8
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N0d3b9490d9754914a153f42914d7f0e5 schema:name Springer Nature
50 rdf:type schema:Organisation
51 N27164e33b35c4743a2e538ba645733e6 schema:familyName Sack
52 schema:givenName Jörg-Rüdiger
53 rdf:type schema:Person
54 N4baa664dc571431e805d35a0e02bbd4a schema:name dimensions_id
55 schema:value pub.1026258834
56 rdf:type schema:PropertyValue
57 N6479fef8a638431d9daef7c9cf4e75c0 schema:familyName Tóth
58 schema:givenName Csaba D.
59 rdf:type schema:Person
60 N6639715019254eb6ac673d52ac0530cb rdf:first N825b9e421ce8493f91301c97453fade7
61 rdf:rest N98c6e65670b847e19d19aaf60a3ccad1
62 N6a5f6dd042d047cfa8ac278dd5bac895 rdf:first Nbf70d747fafe4afaa100dee12289cafc
63 rdf:rest N6639715019254eb6ac673d52ac0530cb
64 N6c35dabeed8b435db3ac939fd1ca801d schema:name doi
65 schema:value 10.1007/978-3-642-03367-4_8
66 rdf:type schema:PropertyValue
67 N825b9e421ce8493f91301c97453fade7 schema:familyName Gavrilova
68 schema:givenName Marina
69 rdf:type schema:Person
70 N8a14838048234c358917f3b7a52b24cf schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N92f97e9d9ad64c11abd9276d53a0f388 rdf:first sg:person.011636042271.02
73 rdf:rest Nfaa229f7b07a4676b04589ef0d197802
74 N98c6e65670b847e19d19aaf60a3ccad1 rdf:first N27164e33b35c4743a2e538ba645733e6
75 rdf:rest Nf61c57157a134f51a31b9d4e8a6933e5
76 Nbf70d747fafe4afaa100dee12289cafc schema:familyName Dehne
77 schema:givenName Frank
78 rdf:type schema:Person
79 Ne84505945afd45d8bce85c86c8192dba schema:isbn 978-3-642-03366-7
80 978-3-642-03367-4
81 schema:name Algorithms and Data Structures
82 rdf:type schema:Book
83 Nf61c57157a134f51a31b9d4e8a6933e5 rdf:first N6479fef8a638431d9daef7c9cf4e75c0
84 rdf:rest rdf:nil
85 Nfaa229f7b07a4676b04589ef0d197802 rdf:first sg:person.01121041073.51
86 rdf:rest rdf:nil
87 Nfc85fed6dca245e7a278a00a03141a2e rdf:first sg:person.01274506210.27
88 rdf:rest N92f97e9d9ad64c11abd9276d53a0f388
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.01121041073.51 schema:affiliation grid-institutes:grid.256304.6
96 schema:familyName Zelikovsky
97 schema:givenName Alexander
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
99 rdf:type schema:Person
100 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
101 schema:familyName Karpinski
102 schema:givenName Marek
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
104 rdf:type schema:Person
105 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
106 schema:familyName Berman
107 schema:givenName Piotr
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
109 rdf:type schema:Person
110 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, 53117, Bonn, Germany
111 schema:name Department of Computer Science, University of Bonn, 53117, Bonn, Germany
112 rdf:type schema:Organization
113 grid-institutes:grid.256304.6 schema:alternateName Department of Computer Science, Georgia State University, 30303, Atlanta, GA, USA
114 schema:name Department of Computer Science, Georgia State University, 30303, Atlanta, GA, USA
115 rdf:type schema:Organization
116 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science & Engineering, Pennsylvania State University, University Park, 16802, PA, USA
117 schema:name Department of Computer Science & Engineering, Pennsylvania State University, University Park, 16802, PA, USA
118 rdf:type schema:Organization
 




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


...