On the Full and Bottleneck Full Steiner Tree Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Yen Hung Chen , Chin Lung Lu , Chuan Yi Tang

ABSTRACT

Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree problem is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. In this paper, we present a new approximation algorithm with performance ratio 2ρ for the full Steiner tree problem, where ρ is the best-known performance ratio for the Steiner tree problem. Moreover, we give an exact algorithm of O(|E| log |E|) time to solve the bottleneck full Steiner tree problem. More... »

PAGES

122-129

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-40534-4
978-3-540-45071-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45071-8_14

DOI

http://dx.doi.org/10.1007/3-540-45071-8_14

DIMENSIONS

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


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/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Yen Hung", 
        "id": "sg:person.01347725471.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Chiao Tung University", 
          "id": "https://www.grid.ac/institutes/grid.260539.b", 
          "name": [
            "Department of Biological Science and Technology, National Chiao Tung University, Hsinchu, 300, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Chin Lung", 
        "id": "sg:person.016502771037.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Chuan Yi", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1023/a:1009758919736", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004234523", 
          "https://doi.org/10.1023/a:1009758919736"
        ], 
        "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"
      }, 
      {
        "id": "sg:pub.10.1007/bf01187035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025618982", 
          "https://doi.org/10.1007/bf01187035"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(96)00113-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026864866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1994.1041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033106374"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(03)00209-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033673857"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(03)00209-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033673857"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/274535.274536", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040427822"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0020-0190(02)00227-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040472536"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.2000.1086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042397506"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(93)90201-j", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042557597"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1048681974", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2363-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048681974", 
          "https://doi.org/10.1007/978-1-4757-2363-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2363-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048681974", 
          "https://doi.org/10.1007/978-1-4757-2363-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/43.62776", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061173685"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0132072", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062839610"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539795281086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880011"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree problem is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. In this paper, we present a new approximation algorithm with performance ratio 2\u03c1 for the full Steiner tree problem, where \u03c1 is the best-known performance ratio for the Steiner tree problem. Moreover, we give an exact algorithm of O(|E| log |E|) time to solve the bottleneck full Steiner tree problem.", 
    "editor": [
      {
        "familyName": "Warnow", 
        "givenName": "Tandy", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45071-8_14", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40534-4", 
        "978-3-540-45071-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "On the Full and Bottleneck Full Steiner Tree Problems", 
    "pagination": "122-129", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45071-8_14"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0fa5f9be4962d99e1e979b276c22c92a6aa151d862d6f53495b3e4ecf917b6ce"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003285132"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45071-8_14", 
      "https://app.dimensions.ai/details/publication/pub.1003285132"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T18:46", 
    "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/0000000001_0000000264/records_8681_00000558.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-45071-8_14"
  }
]
 

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/3-540-45071-8_14'

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/3-540-45071-8_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45071-8_14'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45071-8_14'


 

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

131 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45071-8_14 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N41782c3aae3e4328851baa64d9184b55
4 schema:citation sg:pub.10.1007/978-1-4757-2363-2
5 sg:pub.10.1007/bf01187035
6 sg:pub.10.1023/a:1009758919736
7 https://app.dimensions.ai/details/publication/pub.1048681974
8 https://doi.org/10.1006/jagm.1994.1041
9 https://doi.org/10.1006/jagm.2000.1086
10 https://doi.org/10.1016/0020-0190(93)90201-j
11 https://doi.org/10.1016/s0020-0190(02)00227-2
12 https://doi.org/10.1016/s0304-3975(03)00209-3
13 https://doi.org/10.1016/s0377-2217(96)00113-0
14 https://doi.org/10.1109/43.62776
15 https://doi.org/10.1137/0132072
16 https://doi.org/10.1137/s0097539795281086
17 https://doi.org/10.1145/274535.274536
18 schema:datePublished 2003
19 schema:datePublishedReg 2003-01-01
20 schema:description Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree problem is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. In this paper, we present a new approximation algorithm with performance ratio 2ρ for the full Steiner tree problem, where ρ is the best-known performance ratio for the Steiner tree problem. Moreover, we give an exact algorithm of O(|E| log |E|) time to solve the bottleneck full Steiner tree problem.
21 schema:editor Nd6ee360bb4f54832bd631632e447b080
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N65a5a6582fd74cf585d675f8fe3d43dd
26 schema:name On the Full and Bottleneck Full Steiner Tree Problems
27 schema:pagination 122-129
28 schema:productId N56a10ea5df734fe1a47233933e49335b
29 N98c32c18d2b94814a80984375e196545
30 Ne0ef1345d4004cf0b2cc77c1e1384ee1
31 schema:publisher N150f82c26f5f4595b0963d98d985d054
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003285132
33 https://doi.org/10.1007/3-540-45071-8_14
34 schema:sdDatePublished 2019-04-15T18:46
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N365025043b304b58b344a354d2fa4346
37 schema:url http://link.springer.com/10.1007/3-540-45071-8_14
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N150f82c26f5f4595b0963d98d985d054 schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N365025043b304b58b344a354d2fa4346 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N3abb1870373e4a5290b2d54686bc14c2 rdf:first N8ea5e2da27ca4de681e4866ea21f7b0f
47 rdf:rest rdf:nil
48 N41782c3aae3e4328851baa64d9184b55 rdf:first sg:person.01347725471.75
49 rdf:rest Nc4e5447e041447a0b816d7f8c2fbf917
50 N56a10ea5df734fe1a47233933e49335b schema:name doi
51 schema:value 10.1007/3-540-45071-8_14
52 rdf:type schema:PropertyValue
53 N65a5a6582fd74cf585d675f8fe3d43dd schema:isbn 978-3-540-40534-4
54 978-3-540-45071-9
55 schema:name Computing and Combinatorics
56 rdf:type schema:Book
57 N8ea5e2da27ca4de681e4866ea21f7b0f schema:familyName Zhu
58 schema:givenName Binhai
59 rdf:type schema:Person
60 N98c32c18d2b94814a80984375e196545 schema:name readcube_id
61 schema:value 0fa5f9be4962d99e1e979b276c22c92a6aa151d862d6f53495b3e4ecf917b6ce
62 rdf:type schema:PropertyValue
63 Nb7951605f9cb478da049e97ce93c5742 rdf:first sg:person.01312526135.27
64 rdf:rest rdf:nil
65 Nba092cfefe8e4a0e8aa964dbfd737811 schema:familyName Warnow
66 schema:givenName Tandy
67 rdf:type schema:Person
68 Nc4e5447e041447a0b816d7f8c2fbf917 rdf:first sg:person.016502771037.22
69 rdf:rest Nb7951605f9cb478da049e97ce93c5742
70 Nd6ee360bb4f54832bd631632e447b080 rdf:first Nba092cfefe8e4a0e8aa964dbfd737811
71 rdf:rest N3abb1870373e4a5290b2d54686bc14c2
72 Ne0ef1345d4004cf0b2cc77c1e1384ee1 schema:name dimensions_id
73 schema:value pub.1003285132
74 rdf:type schema:PropertyValue
75 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
76 schema:name Biological Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
79 schema:name Plant Biology
80 rdf:type schema:DefinedTerm
81 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
82 schema:familyName Tang
83 schema:givenName Chuan Yi
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
85 rdf:type schema:Person
86 sg:person.01347725471.75 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
87 schema:familyName Chen
88 schema:givenName Yen Hung
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75
90 rdf:type schema:Person
91 sg:person.016502771037.22 schema:affiliation https://www.grid.ac/institutes/grid.260539.b
92 schema:familyName Lu
93 schema:givenName Chin Lung
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22
95 rdf:type schema:Person
96 sg:pub.10.1007/978-1-4757-2363-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048681974
97 https://doi.org/10.1007/978-1-4757-2363-2
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bf01187035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025618982
100 https://doi.org/10.1007/bf01187035
101 rdf:type schema:CreativeWork
102 sg:pub.10.1023/a:1009758919736 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004234523
103 https://doi.org/10.1023/a:1009758919736
104 rdf:type schema:CreativeWork
105 https://app.dimensions.ai/details/publication/pub.1048681974 schema:CreativeWork
106 https://doi.org/10.1006/jagm.1994.1041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033106374
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1006/jagm.2000.1086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042397506
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0020-0190(93)90201-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1042557597
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0020-0190(02)00227-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040472536
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0304-3975(03)00209-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033673857
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0377-2217(96)00113-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026864866
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/43.62776 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061173685
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/0132072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839610
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/s0097539795281086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880011
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/274535.274536 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040427822
125 rdf:type schema:CreativeWork
126 https://www.grid.ac/institutes/grid.260539.b schema:alternateName National Chiao Tung University
127 schema:name Department of Biological Science and Technology, National Chiao Tung University, Hsinchu, 300, Taiwan, R.O.C
128 rdf:type schema:Organization
129 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
130 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C
131 rdf:type schema:Organization
 




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


...