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-10-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_212.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 Nca40108518c247d5af67ed0a6c71b10d
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 Na66b5b746e794f1fa859a3c03f43b72c
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N9116d4c6f32846b39421e4f96f8d503f
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 N95e425b36e22446f90311ce2b20a069e
38 Ne29b0525dd8b4ed894ebc1c50dcbdd94
39 schema:publisher N08af8f1ae78e4554b82b59c399b5e1e7
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-10-01T06:54
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N486a1d5603c04cf19d97c0b6f4c43bc8
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 N08af8f1ae78e4554b82b59c399b5e1e7 schema:name Springer Nature
50 rdf:type schema:Organisation
51 N09127af045bd4c60bad510a3799de8e8 schema:familyName Dehne
52 schema:givenName Frank
53 rdf:type schema:Person
54 N1c322ba40ba443da930a10d57514c75c schema:familyName Sack
55 schema:givenName Jörg-Rüdiger
56 rdf:type schema:Person
57 N306e1bc2f6de4df2932d466916eb45d5 rdf:first sg:person.01121041073.51
58 rdf:rest rdf:nil
59 N383196fe724d4380a9e02e04d7208bee rdf:first Nc287c0ab64184fe39a34ea8a85be673b
60 rdf:rest rdf:nil
61 N486a1d5603c04cf19d97c0b6f4c43bc8 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N620075350ff54558951005d0f8fb875f schema:familyName Gavrilova
64 schema:givenName Marina
65 rdf:type schema:Person
66 N8d2c448e15a5485baef76fd4241f4129 rdf:first sg:person.011636042271.02
67 rdf:rest N306e1bc2f6de4df2932d466916eb45d5
68 N9116d4c6f32846b39421e4f96f8d503f schema:isbn 978-3-642-03366-7
69 978-3-642-03367-4
70 schema:name Algorithms and Data Structures
71 rdf:type schema:Book
72 N95e425b36e22446f90311ce2b20a069e schema:name doi
73 schema:value 10.1007/978-3-642-03367-4_8
74 rdf:type schema:PropertyValue
75 Na66b5b746e794f1fa859a3c03f43b72c rdf:first N09127af045bd4c60bad510a3799de8e8
76 rdf:rest Nb2b52467c5224c55b13fe18471f4686e
77 Nb2b52467c5224c55b13fe18471f4686e rdf:first N620075350ff54558951005d0f8fb875f
78 rdf:rest Nea32da3a13fa477cb8f0b9ef5305292e
79 Nc287c0ab64184fe39a34ea8a85be673b schema:familyName Tóth
80 schema:givenName Csaba D.
81 rdf:type schema:Person
82 Nca40108518c247d5af67ed0a6c71b10d rdf:first sg:person.01274506210.27
83 rdf:rest N8d2c448e15a5485baef76fd4241f4129
84 Ne29b0525dd8b4ed894ebc1c50dcbdd94 schema:name dimensions_id
85 schema:value pub.1026258834
86 rdf:type schema:PropertyValue
87 Nea32da3a13fa477cb8f0b9ef5305292e rdf:first N1c322ba40ba443da930a10d57514c75c
88 rdf:rest N383196fe724d4380a9e02e04d7208bee
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)


...