Ontology type: schema:ScholarlyArticle Open Access: True
2018-12-11
AUTHORSZhi-Zhong Chen, Guohui Lin, Lusheng Wang, Yong Chen, Dan Wang
ABSTRACTGiven 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... »
PAGES4167-4199
http://scigraph.springernature.com/pub.10.1007/s00453-018-00533-w
DOIhttp://dx.doi.org/10.1007/s00453-018-00533-w
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1110535568
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/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",
"volumeNumber": "81"
}
],
"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",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"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"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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'
Turtle is a human-readable linked data format.
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