A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2 View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Piotr Berman , Marek Karpinski , Alexander Zelikovsky

ABSTRACT

Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard. More... »

PAGES

15-24

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_4

DOI

http://dx.doi.org/10.1007/978-3-642-17517-6_4

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational 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": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.", 
    "editor": [
      {
        "familyName": "Cheong", 
        "givenName": "Otfried", 
        "type": "Person"
      }, 
      {
        "familyName": "Chwa", 
        "givenName": "Kyung-Yong", 
        "type": "Person"
      }, 
      {
        "familyName": "Park", 
        "givenName": "Kunsoo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-17517-6_4", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-17516-9", 
        "978-3-642-17517-6"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "generalized Steiner tree problem", 
      "Steiner tree problem", 
      "class of graphs", 
      "tree problem", 
      "complete graph", 
      "approximation ratio", 
      "set of pairs", 
      "first algorithm", 
      "graph", 
      "MAX SNP", 
      "length 1", 
      "Steiner tree", 
      "edge length", 
      "algorithm", 
      "problem", 
      "vertices", 
      "subgraphs", 
      "class", 
      "set", 
      "pairs", 
      "length", 
      "requirements", 
      "trees", 
      "ratio", 
      "SNPs"
    ], 
    "name": "A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2", 
    "pagination": "15-24", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010857272"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-17517-6_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-17517-6_4", 
      "https://app.dimensions.ai/details/publication/pub.1010857272"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:20", 
    "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_392.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-17517-6_4"
  }
]
 

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-17517-6_4'

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-17517-6_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_4'

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-17517-6_4'


 

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

114 TRIPLES      22 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-17517-6_4 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nc1a381cb06e642328695e8aab8cef39f
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.
7 schema:editor Ne2e4bbd7a9144d1a9f2ed5a82e4b113c
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N0ae0aba208df4367b1f883b1e9aa0ceb
11 schema:keywords MAX SNP
12 SNPs
13 Steiner tree
14 Steiner tree problem
15 algorithm
16 approximation ratio
17 class
18 class of graphs
19 complete graph
20 edge length
21 first algorithm
22 generalized Steiner tree problem
23 graph
24 length
25 length 1
26 pairs
27 problem
28 ratio
29 requirements
30 set
31 set of pairs
32 subgraphs
33 tree problem
34 trees
35 vertices
36 schema:name A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2
37 schema:pagination 15-24
38 schema:productId N10388e885d4a47d8b37a6ff2d0136d45
39 N9374ac0b12694e05bc68888c9e156557
40 schema:publisher N8ba1acc3b108494b9cf8f5a0da048454
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010857272
42 https://doi.org/10.1007/978-3-642-17517-6_4
43 schema:sdDatePublished 2022-08-04T17:20
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N2f4dca302f5148e6aa9ae58163e3d2b6
46 schema:url https://doi.org/10.1007/978-3-642-17517-6_4
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N0ae0aba208df4367b1f883b1e9aa0ceb schema:isbn 978-3-642-17516-9
51 978-3-642-17517-6
52 schema:name Algorithms and Computation
53 rdf:type schema:Book
54 N10388e885d4a47d8b37a6ff2d0136d45 schema:name doi
55 schema:value 10.1007/978-3-642-17517-6_4
56 rdf:type schema:PropertyValue
57 N204d3f338a784b9b8cdd2fb994f96b38 rdf:first sg:person.011636042271.02
58 rdf:rest N2e63b29a6cc8427682b3cb83985f3c1d
59 N2e63b29a6cc8427682b3cb83985f3c1d rdf:first sg:person.01121041073.51
60 rdf:rest rdf:nil
61 N2f4dca302f5148e6aa9ae58163e3d2b6 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N60ae109f23974105aaeae20c4e83e290 schema:familyName Cheong
64 schema:givenName Otfried
65 rdf:type schema:Person
66 N7845e9cb5c5140899e394111e409a7eb schema:familyName Park
67 schema:givenName Kunsoo
68 rdf:type schema:Person
69 N822e77984dc6450c89fea4e36a9a42b4 rdf:first N7845e9cb5c5140899e394111e409a7eb
70 rdf:rest rdf:nil
71 N8ba1acc3b108494b9cf8f5a0da048454 schema:name Springer Nature
72 rdf:type schema:Organisation
73 N9374ac0b12694e05bc68888c9e156557 schema:name dimensions_id
74 schema:value pub.1010857272
75 rdf:type schema:PropertyValue
76 Nc1a381cb06e642328695e8aab8cef39f rdf:first sg:person.01274506210.27
77 rdf:rest N204d3f338a784b9b8cdd2fb994f96b38
78 Ne2e4bbd7a9144d1a9f2ed5a82e4b113c rdf:first N60ae109f23974105aaeae20c4e83e290
79 rdf:rest Nec06fc2476de4f75a3b4a30bea97c251
80 Nec06fc2476de4f75a3b4a30bea97c251 rdf:first Nef2e7afdfe0a43bcb2ca929e5a41818e
81 rdf:rest N822e77984dc6450c89fea4e36a9a42b4
82 Nef2e7afdfe0a43bcb2ca929e5a41818e schema:familyName Chwa
83 schema:givenName Kyung-Yong
84 rdf:type schema:Person
85 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
86 schema:name Mathematical Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
89 schema:name Numerical and Computational Mathematics
90 rdf:type schema:DefinedTerm
91 sg:person.01121041073.51 schema:affiliation grid-institutes:grid.256304.6
92 schema:familyName Zelikovsky
93 schema:givenName Alexander
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
95 rdf:type schema:Person
96 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
97 schema:familyName Karpinski
98 schema:givenName Marek
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
100 rdf:type schema:Person
101 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
102 schema:familyName Berman
103 schema:givenName Piotr
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
105 rdf:type schema:Person
106 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, 53117, Bonn, Germany
107 schema:name Department of Computer Science, University of Bonn, 53117, Bonn, Germany
108 rdf:type schema:Organization
109 grid-institutes:grid.256304.6 schema:alternateName Department of Computer Science, Georgia State University, 30303, Atlanta, GA, USA
110 schema:name Department of Computer Science, Georgia State University, 30303, Atlanta, GA, USA
111 rdf:type schema:Organization
112 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science & Engineering, Pennsylvania State University, University Park, 16802, PA, USA
113 schema:name Department of Computer Science & Engineering, Pennsylvania State University, University Park, 16802, PA, USA
114 rdf:type schema:Organization
 




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


...