On the Clustered Steiner Tree Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Bang Ye Wu

ABSTRACT

We investigate the Clustered Steiner tree problem on metric graphs, which is a variant of Steiner minimum tree problem. The required vertices are partitioned into clusters, and in a feasible clustered Steiner tree, the subtrees spanning two different clusters must be disjoint. In this paper, we show that the problem remains NP-hard even if the topologies of all clusters and the inter-cluster tree are given. We propose a (ρ + 2)-approximation algorithm for the general case, in which ρ is the approximation ratio for the Steiner tree problem. When the topologies for all clusters are given, we show a (ρ + 1)-approximation algorithm. We also discuss the Steiner ratio for this problem. We show the ratio is lower and upper bounded by three and four, respectively. More... »

PAGES

60-71

Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-319-03779-0
978-3-319-03780-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_6

DOI

http://dx.doi.org/10.1007/978-3-319-03780-6_6

DIMENSIONS

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


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": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We investigate the Clustered Steiner tree problem on metric graphs, which is a variant of Steiner minimum tree problem. The required vertices are partitioned into clusters, and in a feasible clustered Steiner tree, the subtrees spanning two different clusters must be disjoint. In this paper, we show that the problem remains NP-hard even if the topologies of all clusters and the inter-cluster tree are given. We propose a (\u03c1\u2009+\u20092)-approximation algorithm for the general case, in which \u03c1 is the approximation ratio for the Steiner tree problem. When the topologies for all clusters are given, we show a (\u03c1\u2009+\u20091)-approximation algorithm. We also discuss the Steiner ratio for this problem. We show the ratio is lower and upper bounded by three and four, respectively.", 
    "editor": [
      {
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Xu", 
        "givenName": "Yinfeng", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-03780-6_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-03779-0", 
        "978-3-319-03780-6"
      ], 
      "name": "Combinatorial Optimization and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "ratio", 
      "variants", 
      "cases", 
      "clusters", 
      "problem", 
      "different clusters", 
      "trees", 
      "NP", 
      "paper", 
      "algorithm", 
      "vertices", 
      "Steiner tree problem", 
      "tree problem", 
      "graph", 
      "metric graphs", 
      "general case", 
      "approximation ratio", 
      "Steiner ratio", 
      "Steiner minimum tree problem", 
      "Steiner tree", 
      "disjoint", 
      "topology", 
      "subtrees", 
      "Clustered Steiner tree problem", 
      "minimum tree problem", 
      "inter-cluster tree"
    ], 
    "name": "On the Clustered Steiner Tree Problem", 
    "pagination": "60-71", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047233793"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-03780-6_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-03780-6_6", 
      "https://app.dimensions.ai/details/publication/pub.1047233793"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_271.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-03780-6_6"
  }
]
 

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-319-03780-6_6'

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-319-03780-6_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_6'

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-319-03780-6_6'


 

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

96 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-03780-6_6 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N58e0de0320874301b81e8f29e2e7da0e
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We investigate the Clustered Steiner tree problem on metric graphs, which is a variant of Steiner minimum tree problem. The required vertices are partitioned into clusters, and in a feasible clustered Steiner tree, the subtrees spanning two different clusters must be disjoint. In this paper, we show that the problem remains NP-hard even if the topologies of all clusters and the inter-cluster tree are given. We propose a (ρ + 2)-approximation algorithm for the general case, in which ρ is the approximation ratio for the Steiner tree problem. When the topologies for all clusters are given, we show a (ρ + 1)-approximation algorithm. We also discuss the Steiner ratio for this problem. We show the ratio is lower and upper bounded by three and four, respectively.
7 schema:editor N11e53adbf4a242d797b92a9a570d99d5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N29760e1c5077445484e0b30b9827b637
12 schema:keywords Clustered Steiner tree problem
13 NP
14 Steiner minimum tree problem
15 Steiner ratio
16 Steiner tree
17 Steiner tree problem
18 algorithm
19 approximation ratio
20 cases
21 clusters
22 different clusters
23 disjoint
24 general case
25 graph
26 inter-cluster tree
27 metric graphs
28 minimum tree problem
29 paper
30 problem
31 ratio
32 subtrees
33 topology
34 tree problem
35 trees
36 variants
37 vertices
38 schema:name On the Clustered Steiner Tree Problem
39 schema:pagination 60-71
40 schema:productId N454788d0e8ce453c87b81a6363736cf5
41 Nadfa43124e0d4b0d87e2041a9a73b75c
42 schema:publisher Ne0f985acb58c407b98aa2a76abc317e5
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047233793
44 https://doi.org/10.1007/978-3-319-03780-6_6
45 schema:sdDatePublished 2021-12-01T20:03
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N880cc8c217984807959626d8a5722d67
48 schema:url https://doi.org/10.1007/978-3-319-03780-6_6
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N11e53adbf4a242d797b92a9a570d99d5 rdf:first Nb5f1523a13ee425986091120896fa00a
53 rdf:rest N1c635e6e64da4c2eba4a15e9d17031cd
54 N1c635e6e64da4c2eba4a15e9d17031cd rdf:first Nb7a2eaee995c4918977f1cec7d939c0e
55 rdf:rest Nf6fd84c2911e4a1d9807f3093898f344
56 N29760e1c5077445484e0b30b9827b637 schema:isbn 978-3-319-03779-0
57 978-3-319-03780-6
58 schema:name Combinatorial Optimization and Applications
59 rdf:type schema:Book
60 N41b2679215814e338dbae2c54244ca97 schema:familyName Zhu
61 schema:givenName Binhai
62 rdf:type schema:Person
63 N454788d0e8ce453c87b81a6363736cf5 schema:name doi
64 schema:value 10.1007/978-3-319-03780-6_6
65 rdf:type schema:PropertyValue
66 N58e0de0320874301b81e8f29e2e7da0e rdf:first sg:person.013045767237.23
67 rdf:rest rdf:nil
68 N880cc8c217984807959626d8a5722d67 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nadfa43124e0d4b0d87e2041a9a73b75c schema:name dimensions_id
71 schema:value pub.1047233793
72 rdf:type schema:PropertyValue
73 Nb5f1523a13ee425986091120896fa00a schema:familyName Widmayer
74 schema:givenName Peter
75 rdf:type schema:Person
76 Nb7a2eaee995c4918977f1cec7d939c0e schema:familyName Xu
77 schema:givenName Yinfeng
78 rdf:type schema:Person
79 Ne0f985acb58c407b98aa2a76abc317e5 schema:name Springer Nature
80 rdf:type schema:Organisation
81 Nf6fd84c2911e4a1d9807f3093898f344 rdf:first N41b2679215814e338dbae2c54244ca97
82 rdf:rest rdf:nil
83 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
84 schema:name Mathematical Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
87 schema:name Numerical and Computational Mathematics
88 rdf:type schema:DefinedTerm
89 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
90 schema:familyName Wu
91 schema:givenName Bang Ye
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
93 rdf:type schema:Person
94 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
95 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
96 rdf:type schema:Organization
 




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


...