# Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2018-12-11

AUTHORS ABSTRACT

Given a vertex-weighted connected graph G=(V,E)\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)$$\end{document}, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3-ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/3 - \epsilon$$\end{document}, for any ϵ>0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon > 0$$\end{document}. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm. More... »

PAGES

4167-4199

TITLE

Algorithmica

ISSUE

11-12

VOLUME

81

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-018-00533-w

DOI

http://dx.doi.org/10.1007/s00453-018-00533-w

DIMENSIONS

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

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/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": "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada",
"id": "http://www.grid.ac/institutes/grid.17089.37",
"name": [
"Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada"
],
"type": "Organization"
},
"familyName": "Lin",
"givenName": "Guohui",
"id": "sg:person.01130357621.02",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "City University of Hong Kong Shenzhen Research Institute, Shenzhen Hi-Tech Industrial Park, Nanshan District, Shenzhen, China",
"id": "http://www.grid.ac/institutes/grid.464255.4",
"name": [
"Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China",
"City University of Hong Kong Shenzhen Research Institute, Shenzhen Hi-Tech Industrial Park, Nanshan District, Shenzhen, China"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Lusheng",
"id": "sg:person.01105113721.52",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, 310018, Hangzhou, Zhejiang, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada",
"Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, 310018, Hangzhou, Zhejiang, China"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Yong",
"id": "sg:person.010555136403.19",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China",
"id": "http://www.grid.ac/institutes/grid.35030.35",
"name": [
"Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Dan",
"id": "sg:person.011747627223.07",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011747627223.07"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-662-44777-2_53",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000274920",
"https://doi.org/10.1007/978-3-662-44777-2_53"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-011-9575-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008571231",
"https://doi.org/10.1007/s00453-011-9575-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-13075-0_37",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035359535",
"https://doi.org/10.1007/978-3-319-13075-0_37"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-03367-4_40",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025243568",
"https://doi.org/10.1007/978-3-642-03367-4_40"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-011-9555-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031494108",
"https://doi.org/10.1007/s00453-011-9555-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-21840-3_41",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043411366",
"https://doi.org/10.1007/978-3-319-21840-3_41"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10878-017-0245-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1100399540",
"https://doi.org/10.1007/s10878-017-0245-7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-39817-4_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004271999",
"https://doi.org/10.1007/978-3-319-39817-4_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45078-8_41",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003514994",
"https://doi.org/10.1007/978-3-540-45078-8_41"
],
"type": "CreativeWork"
}
],
"datePublished": "2018-12-11",
"datePublishedReg": "2018-12-11",
"description": "Given a vertex-weighted connected graph G=(V,E)\\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)$$\\end{document}, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13\u00a0/\u00a017. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3-\u03f5\\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}$$1/3 - \\epsilon$$\\end{document}, for any \u03f5>0\\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}$$\\epsilon > 0$$\\end{document}. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-018-00533-w",
"inLanguage": "en",
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.7426977",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.7538013",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.6078852",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8124106",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8306414",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8132243",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "11-12",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"ratio",
"novel relationship",
"weight",
"variants",
"cases",
"total weight",
"relationship",
"problem",
"mist",
"best approximation algorithm",
"approximation algorithm",
"spanning tree problem",
"maximum weight matching",
"tree problem",
"NPs",
"weight matching",
"matching",
"best approximation ratio",
"approximation ratio",
"claw-free graphs",
"special case",
"connected graph",
"internal vertices",
"unweighted variant",
"APX",
"algorithm",
"performance ratio",
"simple algorithm",
"graph",
"tree T",
"vertices",
"paper"
],
"name": "Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem",
"pagination": "4167-4199",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1110535568"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-018-00533-w"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-018-00533-w",
"https://app.dimensions.ai/details/publication/pub.1110535568"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T10:21",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_767.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-018-00533-w"
}
]

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/s00453-018-00533-w'

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/s00453-018-00533-w'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-00533-w'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-00533-w'

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

180 TRIPLES      22 PREDICATES      66 URIs      49 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0103
3 schema:author N36aefe3feac840ef9d7ab56715677691
4 schema:citation sg:pub.10.1007/978-3-319-13075-0_37
5 sg:pub.10.1007/978-3-319-21840-3_41
6 sg:pub.10.1007/978-3-319-39817-4_10
7 sg:pub.10.1007/978-3-540-45078-8_41
8 sg:pub.10.1007/978-3-642-03367-4_40
9 sg:pub.10.1007/978-3-662-44777-2_53
10 sg:pub.10.1007/s00453-011-9555-9
11 sg:pub.10.1007/s00453-011-9575-5
12 sg:pub.10.1007/s10878-017-0245-7
13 schema:datePublished 2018-12-11
14 schema:datePublishedReg 2018-12-11
15 schema:description Given a vertex-weighted connected graph G=(V,E)\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)$$\end{document}, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3-ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/3 - \epsilon$$\end{document}, for any ϵ>0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon > 0$$\end{document}. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.
16 schema:genre article
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N28b5c250b19e4696826f747272a96f1d
21 sg:journal.1047644
22 schema:keywords APX
23 NPs
24 algorithm
25 approximation algorithm
26 approximation ratio
27 best approximation algorithm
28 best approximation ratio
29 cases
30 claw-free graphs
31 connected graph
32 graph
33 internal vertices
34 matching
35 maximum weight matching
36 mist
37 novel relationship
38 paper
39 performance ratio
40 problem
41 ratio
42 relationship
43 simple algorithm
44 spanning tree problem
45 special case
46 total weight
47 tree T
48 tree problem
49 unweighted variant
50 variants
51 vertices
52 weight
53 weight matching
54 schema:name Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem
55 schema:pagination 4167-4199
56 schema:productId Nca7d5a87c61e4178a33033ee6e3a1c2e
57 Nf5c60a55339d463b8808d151db93f70c
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110535568
59 https://doi.org/10.1007/s00453-018-00533-w
60 schema:sdDatePublished 2022-05-10T10:21
62 schema:sdPublisher N4cb6013a87bb45f99322eb12b4befc7d
63 schema:url https://doi.org/10.1007/s00453-018-00533-w
65 sgo:sdDataset articles
66 rdf:type schema:ScholarlyArticle
67 N049d226c8aa44e7f819662dfd0ca8c74 rdf:first sg:person.011747627223.07
68 rdf:rest rdf:nil
70 rdf:type schema:PublicationVolume
71 N36364cdd67474cf0be97880e3144ea13 rdf:first sg:person.01130357621.02
72 rdf:rest N7a158d0021124cc68d4fa95e15020c83
73 N36aefe3feac840ef9d7ab56715677691 rdf:first sg:person.015654265661.98
74 rdf:rest N36364cdd67474cf0be97880e3144ea13
75 N4cb6013a87bb45f99322eb12b4befc7d schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N7a158d0021124cc68d4fa95e15020c83 rdf:first sg:person.01105113721.52
80 rdf:rest N049d226c8aa44e7f819662dfd0ca8c74
82 rdf:type schema:PublicationIssue
83 Nca7d5a87c61e4178a33033ee6e3a1c2e schema:name doi
84 schema:value 10.1007/s00453-018-00533-w
85 rdf:type schema:PropertyValue
86 Nf5c60a55339d463b8808d151db93f70c schema:name dimensions_id
87 schema:value pub.1110535568
88 rdf:type schema:PropertyValue
89 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
90 schema:name Mathematical Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
93 schema:name Numerical and Computational Mathematics
94 rdf:type schema:DefinedTerm
95 sg:grant.6078852 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-00533-w
96 rdf:type schema:MonetaryGrant
97 sg:grant.7426977 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-00533-w
98 rdf:type schema:MonetaryGrant
99 sg:grant.7538013 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-00533-w
100 rdf:type schema:MonetaryGrant
101 sg:grant.8124106 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-00533-w
102 rdf:type schema:MonetaryGrant
103 sg:grant.8132243 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-00533-w
104 rdf:type schema:MonetaryGrant
105 sg:grant.8306414 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-00533-w
106 rdf:type schema:MonetaryGrant
107 sg:journal.1047644 schema:issn 0178-4617
108 1432-0541
109 schema:name Algorithmica
110 schema:publisher Springer Nature
111 rdf:type schema:Periodical
112 sg:person.010555136403.19 schema:affiliation grid-institutes:grid.411963.8
113 schema:familyName Chen
114 schema:givenName Yong
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19
116 rdf:type schema:Person
117 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.464255.4
118 schema:familyName Wang
119 schema:givenName Lusheng
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
121 rdf:type schema:Person
122 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
123 schema:familyName Lin
124 schema:givenName Guohui
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
126 rdf:type schema:Person
127 sg:person.011747627223.07 schema:affiliation grid-institutes:grid.35030.35
128 schema:familyName Wang
129 schema:givenName Dan
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011747627223.07
131 rdf:type schema:Person
132 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
133 schema:familyName Chen
134 schema:givenName Zhi-Zhong
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
136 rdf:type schema:Person
137 sg:pub.10.1007/978-3-319-13075-0_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035359535
138 https://doi.org/10.1007/978-3-319-13075-0_37
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/978-3-319-21840-3_41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043411366
141 https://doi.org/10.1007/978-3-319-21840-3_41
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/978-3-319-39817-4_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004271999
144 https://doi.org/10.1007/978-3-319-39817-4_10
145 rdf:type schema:CreativeWork
146 sg:pub.10.1007/978-3-540-45078-8_41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003514994
147 https://doi.org/10.1007/978-3-540-45078-8_41
148 rdf:type schema:CreativeWork
149 sg:pub.10.1007/978-3-642-03367-4_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025243568
150 https://doi.org/10.1007/978-3-642-03367-4_40
151 rdf:type schema:CreativeWork
152 sg:pub.10.1007/978-3-662-44777-2_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000274920
153 https://doi.org/10.1007/978-3-662-44777-2_53
154 rdf:type schema:CreativeWork
155 sg:pub.10.1007/s00453-011-9555-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031494108
156 https://doi.org/10.1007/s00453-011-9555-9
157 rdf:type schema:CreativeWork
158 sg:pub.10.1007/s00453-011-9575-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008571231
159 https://doi.org/10.1007/s00453-011-9575-5
160 rdf:type schema:CreativeWork
161 sg:pub.10.1007/s10878-017-0245-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100399540
162 https://doi.org/10.1007/s10878-017-0245-7
163 rdf:type schema:CreativeWork
164 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
165 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
166 rdf:type schema:Organization
167 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China
168 schema:name Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China
169 rdf:type schema:Organization
170 grid-institutes:grid.411963.8 schema:alternateName Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, 310018, Hangzhou, Zhejiang, China
171 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
172 Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, 310018, Hangzhou, Zhejiang, China
173 rdf:type schema:Organization
174 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
175 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
176 rdf:type schema:Organization
177 grid-institutes:grid.464255.4 schema:alternateName City University of Hong Kong Shenzhen Research Institute, Shenzhen Hi-Tech Industrial Park, Nanshan District, Shenzhen, China
178 schema:name City University of Hong Kong Shenzhen Research Institute, Shenzhen Hi-Tech Industrial Park, Nanshan District, Shenzhen, China
179 Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China
180 rdf:type schema:Organization