# Approximation Algorithms for 2-Source Minimum Routing Cost k-Tree Problems

Ontology type: schema:Chapter

### Chapter Info

DATE

2007

AUTHORS ABSTRACT

In this paper, we investigate some k-tree problems of graphs with given two sources. Let G = (V,E,w) be an undirected graph with nonnegative edge lengths and two sources s 1, s 2 ∈ V. The first problem is the 2-source minimum routing cost k -tree (2-kMRCT) problem, in which we want to find a tree T = (V T ,E T ) spanning k vertices such that the total distance from all vertex in V T to the two sources is minimized, i.e., we want to minimize $$\sum_{v\in V_T} \{d_T(s_1,v)+ d_T(s_2,v)\}$$, in which d T (s,v) is the length of the path between s and v on T. The second problem is the 2-source bottleneck source routing cost k -tree (2-kBSRT) problem, in which the objective function is the maximum total distance from any source to all vertices in V T , i.e., $$\max_{s\in (s_1,s_2)} \{ \sum_{v\in V_T} d_T(s,v) \}$$. The third problem is the 2-source bottleneck vertex routing cost k -tree (2-kBVRT) problem, in which the objective function is the maximum total distance from any vertex in V T to the two sources , i.e., $$\max_{v\in V_T}\left\{ d_T(s_1,v)+d_T(s_2,v) \right\}$$. In this paper, we present polynomial time approximation schemes (PTASs) for the 2-kMRCT and 2-kBVRT problems. For the 2-kBSRT problem, we give a (2 + ε)-approximation algorithm for any ε> 0. More... »

PAGES

520-533

### References to SciGraph publications

• 2004. Approximation Algorithms for k-Source Bottleneck Routing Cost Spanning Tree Problems in COMPUTATIONAL SCIENCE AND ITS APPLICATIONS – ICCSA 2004
• ### Book

TITLE

Computational Science and Its Applications – ICCSA 2007

ISBN

978-3-540-74482-5

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74484-9_45

DOI

http://dx.doi.org/10.1007/978-3-540-74484-9_45

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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 Taitung University",
"id": "https://www.grid.ac/institutes/grid.412088.7",
"name": [
"Department of Information Science and Management Systems, National Taitung University, 684, Sec.1, Chunghua Rd., Taitung 950, 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 Taitung University",
"id": "https://www.grid.ac/institutes/grid.412088.7",
"name": [
"Department of Information Science and Management Systems, National Taitung University, 684, Sec.1, Chunghua Rd., Taitung 950, Taiwan, R.O.C."
],
"type": "Organization"
},
"familyName": "Liao",
"givenName": "Gwo-Liang",
"id": "sg:person.016165364352.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016165364352.48"
],
"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.1006/jcss.1997.1542",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019869761"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.dam.2003.10.002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025762847"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/net.20103",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035891635"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/net.20103",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035891635"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0020-0190(98)00010-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037469482"
],
"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": "sg:pub.10.1007/978-3-540-24767-8_37",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048075102",
"https://doi.org/10.1007/978-3-540-24767-8_37"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24767-8_37",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048075102",
"https://doi.org/10.1007/978-3-540-24767-8_37"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tnet.2002.803917",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061714323"
],
"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/s009753979732253x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062880186"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/s0895480194266331",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062882954"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1142/s0219265900000056",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062991998"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/sfcs.1996.548489",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095295328"
],
"type": "CreativeWork"
}
],
"datePublished": "2007",
"datePublishedReg": "2007-01-01",
"description": "In this paper, we investigate some k-tree problems of graphs with given two sources. Let G\u2009=\u2009(V,E,w) be an undirected graph with nonnegative edge lengths and two sources s 1, s 2\u2009\u2208\u2009V. The first problem is the 2-source minimum routing cost k -tree (2-kMRCT) problem, in which we want to find a tree T\u2009=\u2009(V T ,E T ) spanning k vertices such that the total distance from all vertex in V T to the two sources is minimized, i.e., we want to minimize \$$\\sum_{v\\in V_T} \\{d_T(s_1,v)+ d_T(s_2,v)\\}\$$, in which d T (s,v) is the length of the path between s and v on T. The second problem is the 2-source bottleneck source routing cost k -tree (2-kBSRT) problem, in which the objective function is the maximum total distance from any source to all vertices in V T , i.e., \$$\\max_{s\\in (s_1,s_2)} \\{ \\sum_{v\\in V_T} d_T(s,v) \\}\$$. The third problem is the 2-source bottleneck vertex routing cost k -tree (2-kBVRT) problem, in which the objective function is the maximum total distance from any vertex in V T to the two sources , i.e., \$$\\max_{v\\in V_T}\\left\\{ d_T(s_1,v)+d_T(s_2,v) \\right\\}\$$. In this paper, we present polynomial time approximation schemes (PTASs) for the 2-kMRCT and 2-kBVRT problems. For the 2-kBSRT problem, we give a (2\u2009+\u2009\u03b5)-approximation algorithm for any \u03b5>\u20090.",
"editor": [
{
"familyName": "Gervasi",
"givenName": "Osvaldo",
"type": "Person"
},
{
"familyName": "Gavrilova",
"givenName": "Marina L.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-74484-9_45",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-74482-5"
],
"name": "Computational Science and Its Applications \u2013 ICCSA 2007",
"type": "Book"
},
"name": "Approximation Algorithms for 2-Source Minimum Routing Cost k-Tree Problems",
"pagination": "520-533",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-74484-9_45"
]
},
{
"type": "PropertyValue",
"value": [
"0b79a2e693c62bd1e1abf779fbc761662ce5d133571d52042df7631a77dbb3c2"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1002410248"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-74484-9_45",
"https://app.dimensions.ai/details/publication/pub.1002410248"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T15:53",
"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_8672_00000552.jsonl",
"type": "Chapter",
}
]

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-74484-9_45'

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-74484-9_45'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74484-9_45'

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-74484-9_45'

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

132 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N10f9224a5e4840f78e8cfb2f4a7f2667
4 schema:citation sg:pub.10.1007/978-3-540-24767-8_37
5 https://doi.org/10.1002/net.20103
6 https://doi.org/10.1002/net.3230080402
7 https://doi.org/10.1006/jcss.1997.1542
8 https://doi.org/10.1016/j.dam.2003.10.002
9 https://doi.org/10.1016/s0020-0190(98)00010-6
10 https://doi.org/10.1016/s0166-218x(02)00420-1
11 https://doi.org/10.1016/s0166-218x(99)00212-7
12 https://doi.org/10.1016/s0196-6774(02)00205-5
13 https://doi.org/10.1109/sfcs.1996.548489
14 https://doi.org/10.1109/tnet.2002.803917
15 https://doi.org/10.1137/0203015
16 https://doi.org/10.1137/s009753979732253x
17 https://doi.org/10.1137/s0895480194266331
18 https://doi.org/10.1142/s0219265900000056
19 schema:datePublished 2007
20 schema:datePublishedReg 2007-01-01
21 schema:description In this paper, we investigate some k-tree problems of graphs with given two sources. Let G = (V,E,w) be an undirected graph with nonnegative edge lengths and two sources s 1, s 2 ∈ V. The first problem is the 2-source minimum routing cost k -tree (2-kMRCT) problem, in which we want to find a tree T = (V T ,E T ) spanning k vertices such that the total distance from all vertex in V T to the two sources is minimized, i.e., we want to minimize $$\sum_{v\in V_T} \{d_T(s_1,v)+ d_T(s_2,v)\}$$, in which d T (s,v) is the length of the path between s and v on T. The second problem is the 2-source bottleneck source routing cost k -tree (2-kBSRT) problem, in which the objective function is the maximum total distance from any source to all vertices in V T , i.e., $$\max_{s\in (s_1,s_2)} \{ \sum_{v\in V_T} d_T(s,v) \}$$. The third problem is the 2-source bottleneck vertex routing cost k -tree (2-kBVRT) problem, in which the objective function is the maximum total distance from any vertex in V T to the two sources , i.e., $$\max_{v\in V_T}\left\{ d_T(s_1,v)+d_T(s_2,v) \right\}$$. In this paper, we present polynomial time approximation schemes (PTASs) for the 2-kMRCT and 2-kBVRT problems. For the 2-kBSRT problem, we give a (2 + ε)-approximation algorithm for any ε> 0.
22 schema:editor N0d5e3fea02f14772854ce9f384a4d7b4
23 schema:genre chapter
24 schema:inLanguage en
25 schema:isAccessibleForFree false
26 schema:isPartOf N875e48ef71634c55a0f8cd3c32480118
27 schema:name Approximation Algorithms for 2-Source Minimum Routing Cost k-Tree Problems
28 schema:pagination 520-533
29 schema:productId N2e0512b7ce634e91ac45965b614c45ce
30 N94bed50db3374ee3b423d2ecbf6c7466
31 Naeff353cf6ce48b790ce2a514d6cb103
32 schema:publisher Nf4b04a81791e499ba3e04afcf32308ce
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002410248
34 https://doi.org/10.1007/978-3-540-74484-9_45
35 schema:sdDatePublished 2019-04-15T15:53
37 schema:sdPublisher N6f896a46e3f94c918921b458c719ae36
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N0d5e3fea02f14772854ce9f384a4d7b4 rdf:first Ne700863ba87d4a87b5f03425fcb3c667
43 rdf:rest Na2098c3a80f64ca8aa450bb022761eed
44 N10f9224a5e4840f78e8cfb2f4a7f2667 rdf:first sg:person.01347725471.75
45 rdf:rest N31b143010d58448a8e7c686b18bb1228
46 N2e0512b7ce634e91ac45965b614c45ce schema:name doi
47 schema:value 10.1007/978-3-540-74484-9_45
48 rdf:type schema:PropertyValue
49 N31b143010d58448a8e7c686b18bb1228 rdf:first sg:person.016165364352.48
51 N3e32015d6d7246c8b4ac20c1cc34fe4c schema:familyName Gavrilova
52 schema:givenName Marina L.
53 rdf:type schema:Person
54 N6f896a46e3f94c918921b458c719ae36 schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N875e48ef71634c55a0f8cd3c32480118 schema:isbn 978-3-540-74482-5
57 schema:name Computational Science and Its Applications – ICCSA 2007
58 rdf:type schema:Book
60 schema:value 0b79a2e693c62bd1e1abf779fbc761662ce5d133571d52042df7631a77dbb3c2
61 rdf:type schema:PropertyValue
63 rdf:rest rdf:nil
64 Na2098c3a80f64ca8aa450bb022761eed rdf:first N3e32015d6d7246c8b4ac20c1cc34fe4c
65 rdf:rest rdf:nil
66 Naeff353cf6ce48b790ce2a514d6cb103 schema:name dimensions_id
67 schema:value pub.1002410248
68 rdf:type schema:PropertyValue
69 Ne700863ba87d4a87b5f03425fcb3c667 schema:familyName Gervasi
70 schema:givenName Osvaldo
71 rdf:type schema:Person
72 Nf4b04a81791e499ba3e04afcf32308ce schema:location Berlin, Heidelberg
73 schema:name Springer Berlin Heidelberg
74 rdf:type schema:Organisation
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
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.412088.7
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.016165364352.48 schema:affiliation https://www.grid.ac/institutes/grid.412088.7
92 schema:familyName Liao
93 schema:givenName Gwo-Liang
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016165364352.48
95 rdf:type schema:Person
96 sg:pub.10.1007/978-3-540-24767-8_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048075102
97 https://doi.org/10.1007/978-3-540-24767-8_37
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1002/net.20103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035891635
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1002/net.3230080402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007364680
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1006/jcss.1997.1542 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019869761
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/j.dam.2003.10.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025762847
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/s0020-0190(98)00010-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037469482
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/s0166-218x(02)00420-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037542509
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/s0166-218x(99)00212-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016493109
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/s0196-6774(02)00205-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006134156
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/sfcs.1996.548489 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095295328
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1109/tnet.2002.803917 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061714323
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1137/0203015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841229
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1137/s009753979732253x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880186
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1137/s0895480194266331 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882954
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1142/s0219265900000056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062991998
126 rdf:type schema:CreativeWork
127 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
128 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, R.O.C.
129 rdf:type schema:Organization
130 https://www.grid.ac/institutes/grid.412088.7 schema:alternateName National Taitung University
131 schema:name Department of Information Science and Management Systems, National Taitung University, 684, Sec.1, Chunghua Rd., Taitung 950, Taiwan, R.O.C.
132 rdf:type schema:Organization