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": "2022-01-01T19:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_180.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 Nfda290e2f45d443c83f5cf3a3118c1da
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 Na5b618ace4ed4f8f9d18855f3e1a1048
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2fda529c93da4a26bbaa01c93784cde6
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 N85ae3777c36f4ea8a546360167969c06
41 N8b912b5432534b23a695ed2f3283a24e
42 schema:publisher N9b1fa17cea3143018b120907f91fd12a
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 2022-01-01T19:11
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N50bd0fea45604e53ac09ea6517e83f71
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 N2fda529c93da4a26bbaa01c93784cde6 schema:isbn 978-3-319-03779-0
53 978-3-319-03780-6
54 schema:name Combinatorial Optimization and Applications
55 rdf:type schema:Book
56 N50bd0fea45604e53ac09ea6517e83f71 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N692a490f605441278f69abee25a3a036 rdf:first Nce6b479a9b05492bb74e79c9f90ec628
59 rdf:rest rdf:nil
60 N85ae3777c36f4ea8a546360167969c06 schema:name doi
61 schema:value 10.1007/978-3-319-03780-6_6
62 rdf:type schema:PropertyValue
63 N8b912b5432534b23a695ed2f3283a24e schema:name dimensions_id
64 schema:value pub.1047233793
65 rdf:type schema:PropertyValue
66 N9b1fa17cea3143018b120907f91fd12a schema:name Springer Nature
67 rdf:type schema:Organisation
68 Na5b618ace4ed4f8f9d18855f3e1a1048 rdf:first Nbba3c42d3bdf40d8979b0eb2a74b700d
69 rdf:rest Nd6a99bb9d9804e0a8fde202b7dc0669c
70 Nbba3c42d3bdf40d8979b0eb2a74b700d schema:familyName Widmayer
71 schema:givenName Peter
72 rdf:type schema:Person
73 Nce6b479a9b05492bb74e79c9f90ec628 schema:familyName Zhu
74 schema:givenName Binhai
75 rdf:type schema:Person
76 Nd6a99bb9d9804e0a8fde202b7dc0669c rdf:first Ne6fa933958ff43969c250e2e6866ae07
77 rdf:rest N692a490f605441278f69abee25a3a036
78 Ne6fa933958ff43969c250e2e6866ae07 schema:familyName Xu
79 schema:givenName Yinfeng
80 rdf:type schema:Person
81 Nfda290e2f45d443c83f5cf3a3118c1da rdf:first sg:person.013045767237.23
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)


...