Approximation Algorithms for Some Optimum Communication Spanning Tree Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001-03-29

AUTHORS

Bang Ye Wu , Kun-Mao Chao , Chuan Yi Tang

ABSTRACT

Let G = (V, E,w) be an undirected graph with nonnegative edge weight w, and r be a nonnegative vertex weight. The productrequirement optimum communication spanning tree (PROCT) problem is to find a spanning tree T minimizing Σi,j∈V r(i)r(j)d(T, i, j), where d(T, i, j) is the distance between i and j on T. The sum-requirement optimum communication spanning tree (SROCT) problem is to minimize Σi,j∈V (r(i) + r(j))d(T, i, j). Both the two problems are special cases of the general optimum communication spanning tree problem, and are generalizations of the shortest total path length spanning tree problem. In this paper, we present an O(n5) time 1.577-approximation algorithm for the PROCT problem, and an O(n3) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices. More... »

PAGES

408-416

Book

TITLE

Algorithms and Computation

ISBN

978-3-540-65385-1
978-3-540-49381-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49381-6_43

DOI

http://dx.doi.org/10.1007/3-540-49381-6_43

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Dept. of Computer Science, National Tsing Hua University Hsinchu, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Providence University", 
          "id": "https://www.grid.ac/institutes/grid.412550.7", 
          "name": [
            "Dept. of Computer Science and Information Management, Providence University Shalu, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chao", 
        "givenName": "Kun-Mao", 
        "id": "sg:person.01063515113.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Dept. of Computer Science, National Tsing Hua University Hsinchu, 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": "https://doi.org/10.1002/net.3230080402", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007364680"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0203015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841229"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0601008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848632"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001-03-29", 
    "datePublishedReg": "2001-03-29", 
    "description": "Let G = (V, E,w) be an undirected graph with nonnegative edge weight w, and r be a nonnegative vertex weight. The productrequirement optimum communication spanning tree (PROCT) problem is to find a spanning tree T minimizing \u03a3i,j\u2208V r(i)r(j)d(T, i, j), where d(T, i, j) is the distance between i and j on T. The sum-requirement optimum communication spanning tree (SROCT) problem is to minimize \u03a3i,j\u2208V (r(i) + r(j))d(T, i, j). Both the two problems are special cases of the general optimum communication spanning tree problem, and are generalizations of the shortest total path length spanning tree problem. In this paper, we present an O(n5) time 1.577-approximation algorithm for the PROCT problem, and an O(n3) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices.", 
    "editor": [
      {
        "familyName": "Chwa", 
        "givenName": "Kyung-Yong", 
        "type": "Person"
      }, 
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar H.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-49381-6_43", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65385-1", 
        "978-3-540-49381-5"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Approximation Algorithms for Some Optimum Communication Spanning Tree Problems", 
    "pagination": "408-416", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-49381-6_43"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d58ba9d4aad433ba27baecffcad799a25b5d979bd4edb764e3071fe6c3f05e7e"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044831210"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-49381-6_43", 
      "https://app.dimensions.ai/details/publication/pub.1044831210"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05: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/0000000347_0000000347/records_89807_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-49381-6_43"
  }
]
 

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-49381-6_43'

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-49381-6_43'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49381-6_43'

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-49381-6_43'


 

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

96 TRIPLES      23 PREDICATES      29 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-49381-6_43 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nf5102443fa8b4855882089bbd1f4a6da
4 schema:citation https://doi.org/10.1002/net.3230080402
5 https://doi.org/10.1137/0203015
6 https://doi.org/10.1137/0601008
7 schema:datePublished 2001-03-29
8 schema:datePublishedReg 2001-03-29
9 schema:description Let G = (V, E,w) be an undirected graph with nonnegative edge weight w, and r be a nonnegative vertex weight. The productrequirement optimum communication spanning tree (PROCT) problem is to find a spanning tree T minimizing Σi,j∈V r(i)r(j)d(T, i, j), where d(T, i, j) is the distance between i and j on T. The sum-requirement optimum communication spanning tree (SROCT) problem is to minimize Σi,j∈V (r(i) + r(j))d(T, i, j). Both the two problems are special cases of the general optimum communication spanning tree problem, and are generalizations of the shortest total path length spanning tree problem. In this paper, we present an O(n5) time 1.577-approximation algorithm for the PROCT problem, and an O(n3) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices.
10 schema:editor N75c96704f5e94108a40bd9871c60fa6f
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree true
14 schema:isPartOf Nc43d52271f664b3ba59cabf7cb5d7be3
15 schema:name Approximation Algorithms for Some Optimum Communication Spanning Tree Problems
16 schema:pagination 408-416
17 schema:productId N2219b84f904d4f18b0d1d026782498a8
18 N976045abe1a14460a93ecbb02246bb9b
19 Nb3287e3b5bf2431ca9114150e63ae541
20 schema:publisher N4d12ccf4ce2e4a7c869340780d1500a9
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044831210
22 https://doi.org/10.1007/3-540-49381-6_43
23 schema:sdDatePublished 2019-04-16T05:46
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher N039e96e45fc0410b92543b6492399568
26 schema:url https://link.springer.com/10.1007%2F3-540-49381-6_43
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N039e96e45fc0410b92543b6492399568 schema:name Springer Nature - SN SciGraph project
31 rdf:type schema:Organization
32 N0ddca74797cf43099b5cf37dde88a61e schema:familyName Ibarra
33 schema:givenName Oscar H.
34 rdf:type schema:Person
35 N2219b84f904d4f18b0d1d026782498a8 schema:name dimensions_id
36 schema:value pub.1044831210
37 rdf:type schema:PropertyValue
38 N4d12ccf4ce2e4a7c869340780d1500a9 schema:location Berlin, Heidelberg
39 schema:name Springer Berlin Heidelberg
40 rdf:type schema:Organisation
41 N6724a608f20446b2b1da3740978f5078 schema:familyName Chwa
42 schema:givenName Kyung-Yong
43 rdf:type schema:Person
44 N75c96704f5e94108a40bd9871c60fa6f rdf:first N6724a608f20446b2b1da3740978f5078
45 rdf:rest N94b1b8db38424a279251a88dcec7e6a0
46 N7912adcf8ead412bba958bc8e33ded85 rdf:first sg:person.01312526135.27
47 rdf:rest rdf:nil
48 N94b1b8db38424a279251a88dcec7e6a0 rdf:first N0ddca74797cf43099b5cf37dde88a61e
49 rdf:rest rdf:nil
50 N976045abe1a14460a93ecbb02246bb9b schema:name readcube_id
51 schema:value d58ba9d4aad433ba27baecffcad799a25b5d979bd4edb764e3071fe6c3f05e7e
52 rdf:type schema:PropertyValue
53 Nb3287e3b5bf2431ca9114150e63ae541 schema:name doi
54 schema:value 10.1007/3-540-49381-6_43
55 rdf:type schema:PropertyValue
56 Nc43d52271f664b3ba59cabf7cb5d7be3 schema:isbn 978-3-540-49381-5
57 978-3-540-65385-1
58 schema:name Algorithms and Computation
59 rdf:type schema:Book
60 Nd60e4cc909184ce5a1be71c20e21314a rdf:first sg:person.01063515113.26
61 rdf:rest N7912adcf8ead412bba958bc8e33ded85
62 Nf5102443fa8b4855882089bbd1f4a6da rdf:first sg:person.013045767237.23
63 rdf:rest Nd60e4cc909184ce5a1be71c20e21314a
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
68 schema:name Numerical and Computational Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.01063515113.26 schema:affiliation https://www.grid.ac/institutes/grid.412550.7
71 schema:familyName Chao
72 schema:givenName Kun-Mao
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.26
74 rdf:type schema:Person
75 sg:person.013045767237.23 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
76 schema:familyName Wu
77 schema:givenName Bang Ye
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
79 rdf:type schema:Person
80 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
81 schema:familyName Tang
82 schema:givenName Chuan Yi
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
84 rdf:type schema:Person
85 https://doi.org/10.1002/net.3230080402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007364680
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1137/0203015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841229
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1137/0601008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848632
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
92 schema:name Dept. of Computer Science, National Tsing Hua University Hsinchu, Taiwan, R.O.C.
93 rdf:type schema:Organization
94 https://www.grid.ac/institutes/grid.412550.7 schema:alternateName Providence University
95 schema:name Dept. of Computer Science and Information Management, Providence University Shalu, Taiwan, R.O.C.
96 rdf:type schema:Organization
 




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


...