Approximation Algorithms for k-Source Bottleneck Routing Cost Spanning Tree Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Yen Hung Chen , Bang Ye Wu , Chuan Yi Tang

ABSTRACT

In this paper, we investigate two spanning tree problems of graphs with k given sources. Let G=(V,E,w) be an undirected graph with nonnegative edge lengths and S ⊂ V a set of k specified sources. The first problem is the k-source bottleneck vertex routing cost spanning tree (k-BVRT) problem, in which we want to find a spanning tree T such that the maximum total distance from any vertex to all sources is minimized, i.e., we want to minimize maxν ∈ v{Σs ∈ SdT(s,υ)}, in which dT(s,v) is the length of the path between s and v on T. The other problem is the k-source bottleneck source routing cost spanning tree (k-BSRT) problem, in which the objective function is the maximum total distance from any source to all vertices, i.e., maxs ∈ S{Σν ∈ VdT(s,υ)}. In this paper, we present a polynomial time approximation scheme (PTAS) for the 2-BVRT problem. For the 2-BSRT problem, we first give (2+ε)-approximation algorithm for any ε> 0, and then present a PTAS for the case that the input graphs are restricted to metric graphs. Finally we show that there is a simple 3-approximation algorithm for both the two problems with arbitrary k. More... »

PAGES

355-366

Book

TITLE

Computational Science and Its Applications – ICCSA 2004

ISBN

978-3-540-22057-2
978-3-540-24767-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24767-8_37

DOI

http://dx.doi.org/10.1007/978-3-540-24767-8_37

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing 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": "Shu-Te University", 
          "id": "https://www.grid.ac/institutes/grid.445041.0", 
          "name": [
            "Department of Computer Science and Information Engineering, Shu-Te University, YenChau Kaoshiung 824, 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": "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": "https://doi.org/10.1016/s0196-6774(02)00205-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006134156"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0196-6774(02)00205-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006134156"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230080402", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007364680"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(99)00212-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016493109"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/316542.316548", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027318638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(02)00420-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037542509"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(02)00420-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037542509"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753979732253x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880186"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0219265900000056", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062991998"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "In this paper, we investigate two spanning tree problems of graphs with k given sources. Let G=(V,E,w) be an undirected graph with nonnegative edge lengths and S \u2282 V a set of k specified sources. The first problem is the k-source bottleneck vertex routing cost spanning tree (k-BVRT) problem, in which we want to find a spanning tree T such that the maximum total distance from any vertex to all sources is minimized, i.e., we want to minimize max\u03bd \u2208 v{\u03a3s \u2208 SdT(s,\u03c5)}, in which dT(s,v) is the length of the path between s and v on T. The other problem is the k-source bottleneck source routing cost spanning tree (k-BSRT) problem, in which the objective function is the maximum total distance from any source to all vertices, i.e., maxs \u2208 S{\u03a3\u03bd \u2208 VdT(s,\u03c5)}. In this paper, we present a polynomial time approximation scheme (PTAS) for the 2-BVRT problem. For the 2-BSRT problem, we first give (2+\u03b5)-approximation algorithm for any \u03b5> 0, and then present a PTAS for the case that the input graphs are restricted to metric graphs. Finally we show that there is a simple 3-approximation algorithm for both the two problems with arbitrary k.", 
    "editor": [
      {
        "familyName": "Lagan\u00e1", 
        "givenName": "Antonio", 
        "type": "Person"
      }, 
      {
        "familyName": "Gavrilova", 
        "givenName": "Marina L.", 
        "type": "Person"
      }, 
      {
        "familyName": "Kumar", 
        "givenName": "Vipin", 
        "type": "Person"
      }, 
      {
        "familyName": "Mun", 
        "givenName": "Youngsong", 
        "type": "Person"
      }, 
      {
        "familyName": "Tan", 
        "givenName": "C. J. Kenneth", 
        "type": "Person"
      }, 
      {
        "familyName": "Gervasi", 
        "givenName": "Osvaldo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24767-8_37", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22057-2", 
        "978-3-540-24767-8"
      ], 
      "name": "Computational Science and Its Applications \u2013 ICCSA 2004", 
      "type": "Book"
    }, 
    "name": "Approximation Algorithms for k-Source Bottleneck Routing Cost Spanning Tree Problems", 
    "pagination": "355-366", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048075102"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24767-8_37"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e5057eddca73367dd972548cbcba65e5598e2d73d5217e3f527c32b37fdcf05c"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24767-8_37", 
      "https://app.dimensions.ai/details/publication/pub.1048075102"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:25", 
    "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/0000000363_0000000363/records_70053_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-24767-8_37"
  }
]
 

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-540-24767-8_37'

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-540-24767-8_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24767-8_37'

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-540-24767-8_37'


 

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

128 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24767-8_37 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb910d0832b3349a6986f117eacfa475c
4 schema:citation https://doi.org/10.1002/net.3230080402
5 https://doi.org/10.1016/s0166-218x(02)00420-1
6 https://doi.org/10.1016/s0166-218x(99)00212-7
7 https://doi.org/10.1016/s0196-6774(02)00205-5
8 https://doi.org/10.1137/s009753979732253x
9 https://doi.org/10.1142/s0219265900000056
10 https://doi.org/10.1145/316542.316548
11 schema:datePublished 2004
12 schema:datePublishedReg 2004-01-01
13 schema:description In this paper, we investigate two spanning tree problems of graphs with k given sources. Let G=(V,E,w) be an undirected graph with nonnegative edge lengths and S ⊂ V a set of k specified sources. The first problem is the k-source bottleneck vertex routing cost spanning tree (k-BVRT) problem, in which we want to find a spanning tree T such that the maximum total distance from any vertex to all sources is minimized, i.e., we want to minimize maxν ∈ v{Σs ∈ SdT(s,υ)}, in which dT(s,v) is the length of the path between s and v on T. The other problem is the k-source bottleneck source routing cost spanning tree (k-BSRT) problem, in which the objective function is the maximum total distance from any source to all vertices, i.e., maxs ∈ S{Σν ∈ VdT(s,υ)}. In this paper, we present a polynomial time approximation scheme (PTAS) for the 2-BVRT problem. For the 2-BSRT problem, we first give (2+ε)-approximation algorithm for any ε> 0, and then present a PTAS for the case that the input graphs are restricted to metric graphs. Finally we show that there is a simple 3-approximation algorithm for both the two problems with arbitrary k.
14 schema:editor N23da45d9d4ed41d1a4e36c1387e3b680
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N6f58691157894c41aacc0d2cdf06b39f
19 schema:name Approximation Algorithms for k-Source Bottleneck Routing Cost Spanning Tree Problems
20 schema:pagination 355-366
21 schema:productId N124fba73c73a42a8bb1239d3be125895
22 N47668392d3ce49f8a958ecb219812abf
23 Nbfa26e68f62042a09849aef98a5d2b20
24 schema:publisher N8c37c4671d01402aa57e3eda8748bc77
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048075102
26 https://doi.org/10.1007/978-3-540-24767-8_37
27 schema:sdDatePublished 2019-04-16T08:25
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher N58e767510cb2491d8e21536f1b527fb1
30 schema:url https://link.springer.com/10.1007%2F978-3-540-24767-8_37
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N006833d2a6344a0ab5c2e0d1ea41c6f3 schema:familyName Kumar
35 schema:givenName Vipin
36 rdf:type schema:Person
37 N0eb579241aa24e89b3d82485a25b2b2e schema:familyName Mun
38 schema:givenName Youngsong
39 rdf:type schema:Person
40 N0effcf13e1d24a6693b622f867e14611 rdf:first N502e8565920b453e8da1148dd203ae4d
41 rdf:rest Ne2da8f38da994f19984a37303aad24b7
42 N124fba73c73a42a8bb1239d3be125895 schema:name readcube_id
43 schema:value e5057eddca73367dd972548cbcba65e5598e2d73d5217e3f527c32b37fdcf05c
44 rdf:type schema:PropertyValue
45 N23da45d9d4ed41d1a4e36c1387e3b680 rdf:first N26329620b5394335b43c3c1bbf6a35a8
46 rdf:rest N0effcf13e1d24a6693b622f867e14611
47 N26329620b5394335b43c3c1bbf6a35a8 schema:familyName Laganá
48 schema:givenName Antonio
49 rdf:type schema:Person
50 N47668392d3ce49f8a958ecb219812abf schema:name doi
51 schema:value 10.1007/978-3-540-24767-8_37
52 rdf:type schema:PropertyValue
53 N4fafd84f97ff45ae84d33b1d8b57e604 schema:familyName Gervasi
54 schema:givenName Osvaldo
55 rdf:type schema:Person
56 N502e8565920b453e8da1148dd203ae4d schema:familyName Gavrilova
57 schema:givenName Marina L.
58 rdf:type schema:Person
59 N50df8db684d64686b7a3e12c89a76278 rdf:first N8ec9c0972d6b4c349e2aba1fd9e07706
60 rdf:rest Nc150c2b20f774ded8192392950b8aba3
61 N58e767510cb2491d8e21536f1b527fb1 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N6f58691157894c41aacc0d2cdf06b39f schema:isbn 978-3-540-22057-2
64 978-3-540-24767-8
65 schema:name Computational Science and Its Applications – ICCSA 2004
66 rdf:type schema:Book
67 N82f7c5d092d44aceb80c8ecdcbc33550 rdf:first sg:person.013045767237.23
68 rdf:rest N85f0d08492814c1b806df8036643608a
69 N85f0d08492814c1b806df8036643608a rdf:first sg:person.01312526135.27
70 rdf:rest rdf:nil
71 N86cb66ae65fd41c88b7073e97e2e0260 rdf:first N0eb579241aa24e89b3d82485a25b2b2e
72 rdf:rest N50df8db684d64686b7a3e12c89a76278
73 N8c37c4671d01402aa57e3eda8748bc77 schema:location Berlin, Heidelberg
74 schema:name Springer Berlin Heidelberg
75 rdf:type schema:Organisation
76 N8ec9c0972d6b4c349e2aba1fd9e07706 schema:familyName Tan
77 schema:givenName C. J. Kenneth
78 rdf:type schema:Person
79 Nb910d0832b3349a6986f117eacfa475c rdf:first sg:person.01347725471.75
80 rdf:rest N82f7c5d092d44aceb80c8ecdcbc33550
81 Nbfa26e68f62042a09849aef98a5d2b20 schema:name dimensions_id
82 schema:value pub.1048075102
83 rdf:type schema:PropertyValue
84 Nc150c2b20f774ded8192392950b8aba3 rdf:first N4fafd84f97ff45ae84d33b1d8b57e604
85 rdf:rest rdf:nil
86 Ne2da8f38da994f19984a37303aad24b7 rdf:first N006833d2a6344a0ab5c2e0d1ea41c6f3
87 rdf:rest N86cb66ae65fd41c88b7073e97e2e0260
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 sg:person.013045767237.23 schema:affiliation https://www.grid.ac/institutes/grid.445041.0
95 schema:familyName Wu
96 schema:givenName Bang Ye
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
98 rdf:type schema:Person
99 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
100 schema:familyName Tang
101 schema:givenName Chuan Yi
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
103 rdf:type schema:Person
104 sg:person.01347725471.75 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
105 schema:familyName Chen
106 schema:givenName Yen Hung
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75
108 rdf:type schema:Person
109 https://doi.org/10.1002/net.3230080402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007364680
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/s0166-218x(02)00420-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037542509
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/s0166-218x(99)00212-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016493109
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/s0196-6774(02)00205-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006134156
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1137/s009753979732253x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880186
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1142/s0219265900000056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062991998
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/316542.316548 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027318638
122 rdf:type schema:CreativeWork
123 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
124 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, R.O.C.
125 rdf:type schema:Organization
126 https://www.grid.ac/institutes/grid.445041.0 schema:alternateName Shu-Te University
127 schema:name Department of Computer Science and Information Engineering, Shu-Te University, YenChau Kaoshiung 824, Taiwan, R.O.C.
128 rdf:type schema:Organization
 




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


...