On the minimum routing cost clustered tree problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-05-12

AUTHORS

Chen-Wan Lin, Bang Ye Wu

ABSTRACT

For an edge-weighted graph G=(V,E,w)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E,w)$$\end{document}, in which the vertices are partitioned into k clusters R={R1,R2,…,Rk}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}$$\end{document}, a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing k-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k-1$$\end{document} edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for k=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=3$$\end{document}. Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters. More... »

PAGES

1106-1121

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10878-016-0026-8

DOI

http://dx.doi.org/10.1007/s10878-016-0026-8

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "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, ROC", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Chen-Wan", 
        "id": "sg:person.015502526722.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015502526722.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
          ], 
          "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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s004530010045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037667918", 
          "https://doi.org/10.1007/s004530010045"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00500-011-0711-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030956782", 
          "https://doi.org/10.1007/s00500-011-0711-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-15612-5_13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044316673", 
          "https://doi.org/10.1007/978-3-319-15612-5_13"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9080-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012135178", 
          "https://doi.org/10.1007/s00453-007-9080-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-09620-9_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019976321", 
          "https://doi.org/10.1007/978-3-319-09620-9_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9674-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023126388", 
          "https://doi.org/10.1007/s00453-012-9674-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10878-014-9772-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004985974", 
          "https://doi.org/10.1007/s10878-014-9772-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01386390", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041716633", 
          "https://doi.org/10.1007/bf01386390"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-14974-5_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019534849", 
          "https://doi.org/10.1007/978-3-319-14974-5_2"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016-05-12", 
    "datePublishedReg": "2016-05-12", 
    "description": "For an edge-weighted graph G=(V,E,w)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G=(V,E,w)$$\\end{document}, in which the vertices are partitioned into k clusters R={R1,R2,\u2026,Rk}\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal {R}=\\{R_1,R_2,\\ldots ,R_k\\}$$\\end{document}, a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing k-1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k-1$$\\end{document} edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for k=3\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k=3$$\\end{document}. Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10878-016-0026-8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "33"
      }
    ], 
    "keywords": [
      "minimum routing cost", 
      "spanning tree", 
      "routing cost", 
      "total distance", 
      "edge-weighted graph", 
      "cases", 
      "tree problem", 
      "cost", 
      "weight", 
      "variants", 
      "function", 
      "different clusters", 
      "number", 
      "clusters k", 
      "NP", 
      "algorithm", 
      "graph", 
      "clusters", 
      "subtrees", 
      "paper", 
      "distance", 
      "pairs", 
      "edge weights", 
      "objective function", 
      "problem", 
      "trees", 
      "inapproximability", 
      "input", 
      "inequality", 
      "vertices", 
      "pair of vertices", 
      "tree T", 
      "triangle inequality"
    ], 
    "name": "On the minimum routing cost clustered tree problem", 
    "pagination": "1106-1121", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022994862"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10878-016-0026-8"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10878-016-0026-8", 
      "https://app.dimensions.ai/details/publication/pub.1022994862"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:35", 
    "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/article/article_695.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10878-016-0026-8"
  }
]
 

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/s10878-016-0026-8'

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/s10878-016-0026-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-016-0026-8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-016-0026-8'


 

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

142 TRIPLES      22 PREDICATES      69 URIs      50 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10878-016-0026-8 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 anzsrc-for:0102
4 anzsrc-for:0103
5 schema:author N85f6787e097c46639472f26700f2a5a3
6 schema:citation sg:pub.10.1007/978-3-319-09620-9_11
7 sg:pub.10.1007/978-3-319-14974-5_2
8 sg:pub.10.1007/978-3-319-15612-5_13
9 sg:pub.10.1007/bf01386390
10 sg:pub.10.1007/s00453-007-9080-z
11 sg:pub.10.1007/s00453-012-9674-y
12 sg:pub.10.1007/s004530010045
13 sg:pub.10.1007/s00500-011-0711-6
14 sg:pub.10.1007/s10878-014-9772-7
15 schema:datePublished 2016-05-12
16 schema:datePublishedReg 2016-05-12
17 schema:description For an edge-weighted graph G=(V,E,w)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E,w)$$\end{document}, in which the vertices are partitioned into k clusters R={R1,R2,…,Rk}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}$$\end{document}, a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing k-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k-1$$\end{document} edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for k=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=3$$\end{document}. Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.
18 schema:genre article
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf N3ed463b5462045f180a37a3c7687d540
22 N4b851b07eb3c41bf90373b068200155d
23 sg:journal.1036683
24 schema:keywords NP
25 algorithm
26 cases
27 clusters
28 clusters k
29 cost
30 different clusters
31 distance
32 edge weights
33 edge-weighted graph
34 function
35 graph
36 inapproximability
37 inequality
38 input
39 minimum routing cost
40 number
41 objective function
42 pair of vertices
43 pairs
44 paper
45 problem
46 routing cost
47 spanning tree
48 subtrees
49 total distance
50 tree T
51 tree problem
52 trees
53 triangle inequality
54 variants
55 vertices
56 weight
57 schema:name On the minimum routing cost clustered tree problem
58 schema:pagination 1106-1121
59 schema:productId Nd32e1d9321564240abaebe5820d6b0aa
60 Nf175c287a47e4f8781d3bf7c4af3b84f
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022994862
62 https://doi.org/10.1007/s10878-016-0026-8
63 schema:sdDatePublished 2021-12-01T19:35
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N70758e4ae574409a8fbe8eb0c38d6e37
66 schema:url https://doi.org/10.1007/s10878-016-0026-8
67 sgo:license sg:explorer/license/
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N3ed463b5462045f180a37a3c7687d540 schema:issueNumber 3
71 rdf:type schema:PublicationIssue
72 N4b851b07eb3c41bf90373b068200155d schema:volumeNumber 33
73 rdf:type schema:PublicationVolume
74 N70758e4ae574409a8fbe8eb0c38d6e37 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N85f6787e097c46639472f26700f2a5a3 rdf:first sg:person.015502526722.57
77 rdf:rest N8e288b16567a411ebac76045813b5531
78 N8e288b16567a411ebac76045813b5531 rdf:first sg:person.013045767237.23
79 rdf:rest rdf:nil
80 Nd32e1d9321564240abaebe5820d6b0aa schema:name doi
81 schema:value 10.1007/s10878-016-0026-8
82 rdf:type schema:PropertyValue
83 Nf175c287a47e4f8781d3bf7c4af3b84f schema:name dimensions_id
84 schema:value pub.1022994862
85 rdf:type schema:PropertyValue
86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
87 schema:name Mathematical Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
90 schema:name Pure Mathematics
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
93 schema:name Applied Mathematics
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
96 schema:name Numerical and Computational Mathematics
97 rdf:type schema:DefinedTerm
98 sg:journal.1036683 schema:issn 1382-6905
99 1573-2886
100 schema:name Journal of Combinatorial Optimization
101 schema:publisher Springer Nature
102 rdf:type schema:Periodical
103 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
104 schema:familyName Wu
105 schema:givenName Bang Ye
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
107 rdf:type schema:Person
108 sg:person.015502526722.57 schema:affiliation grid-institutes:grid.412047.4
109 schema:familyName Lin
110 schema:givenName Chen-Wan
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015502526722.57
112 rdf:type schema:Person
113 sg:pub.10.1007/978-3-319-09620-9_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019976321
114 https://doi.org/10.1007/978-3-319-09620-9_11
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/978-3-319-14974-5_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019534849
117 https://doi.org/10.1007/978-3-319-14974-5_2
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/978-3-319-15612-5_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044316673
120 https://doi.org/10.1007/978-3-319-15612-5_13
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/bf01386390 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716633
123 https://doi.org/10.1007/bf01386390
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/s00453-007-9080-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1012135178
126 https://doi.org/10.1007/s00453-007-9080-z
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/s00453-012-9674-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1023126388
129 https://doi.org/10.1007/s00453-012-9674-y
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/s004530010045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037667918
132 https://doi.org/10.1007/s004530010045
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/s00500-011-0711-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030956782
135 https://doi.org/10.1007/s00500-011-0711-6
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s10878-014-9772-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004985974
138 https://doi.org/10.1007/s10878-014-9772-7
139 rdf:type schema:CreativeWork
140 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
141 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
142 rdf:type schema:Organization
 




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


...