Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2017-07-01

AUTHORS

Zhi-Zhong Chen , Guohui Lin , Lusheng Wang , Yong Chen , Dan Wang

ABSTRACT

Given a vertex-weighted connected graph \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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio \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 \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 the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been previously studied, we design a 7/12-approximation algorithm. More... »

PAGES

124-136

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-62389-4_11

DOI

http://dx.doi.org/10.1007/978-3-319-62389-4_11

DIMENSIONS

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


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/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": "Department of Computer Science, City University of Hong Kong, 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, Tat Chee Avenue, Kowloon, Hong Kong, 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": "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": "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, 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, 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"
      }
    ], 
    "datePublished": "2017-07-01", 
    "datePublishedReg": "2017-07-01", 
    "description": "Given a vertex-weighted connected graph \\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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio \\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 \\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 the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been previously studied, we design a 7/12-approximation algorithm.", 
    "editor": [
      {
        "familyName": "Cao", 
        "givenName": "Yixin", 
        "type": "Person"
      }, 
      {
        "familyName": "Chen", 
        "givenName": "Jianer", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-62389-4_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-62388-7", 
        "978-3-319-62389-4"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "novel relationship", 
      "weight", 
      "variants", 
      "ratio", 
      "cases", 
      "total weight", 
      "relationship", 
      "problem", 
      "mist", 
      "best approximation algorithm", 
      "approximation algorithm", 
      "spanning tree problem", 
      "maximum weight matching", 
      "tree problem", 
      "best approximation ratio", 
      "connected graph", 
      "internal vertices", 
      "unweighted variant", 
      "NPs", 
      "simple algorithm", 
      "weight matching", 
      "matching", 
      "approximation ratio", 
      "claw-free graphs", 
      "special case", 
      "graph", 
      "tree T", 
      "APX", 
      "algorithm", 
      "vertices", 
      "performance ratio", 
      "paper"
    ], 
    "name": "Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem", 
    "pagination": "124-136", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1090448513"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-62389-4_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-62389-4_11", 
      "https://app.dimensions.ai/details/publication/pub.1090448513"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_360.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-62389-4_11"
  }
]
 

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-319-62389-4_11'

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-319-62389-4_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-62389-4_11'

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-319-62389-4_11'


 

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

131 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-62389-4_11 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N7fcfabf1a36a4468b1cf73ab0e49702d
4 schema:datePublished 2017-07-01
5 schema:datePublishedReg 2017-07-01
6 schema:description Given a vertex-weighted connected graph \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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio \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 \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 the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been previously studied, we design a 7/12-approximation algorithm.
7 schema:editor N9a58441117454983b9a1f8b40ef386b9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7e461cd30500444f8eab8035ef60eaa0
12 schema:keywords APX
13 NPs
14 algorithm
15 approximation algorithm
16 approximation ratio
17 best approximation algorithm
18 best approximation ratio
19 cases
20 claw-free graphs
21 connected graph
22 graph
23 internal vertices
24 matching
25 maximum weight matching
26 mist
27 novel relationship
28 paper
29 performance ratio
30 problem
31 ratio
32 relationship
33 simple algorithm
34 spanning tree problem
35 special case
36 total weight
37 tree T
38 tree problem
39 unweighted variant
40 variants
41 vertices
42 weight
43 weight matching
44 schema:name Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem
45 schema:pagination 124-136
46 schema:productId N799c33a4c8ec4f209faa40d18fa469ef
47 Ne10a083d1497413d96e5397fce93a968
48 schema:publisher N3c3fefcadf304b5fab7d3732b13f2d6c
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090448513
50 https://doi.org/10.1007/978-3-319-62389-4_11
51 schema:sdDatePublished 2022-05-20T07:46
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N4453b41831394213b57b9fd88c9d5f97
54 schema:url https://doi.org/10.1007/978-3-319-62389-4_11
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N10dbe3409c11437a934aad762ae1a5f1 rdf:first sg:person.01130357621.02
59 rdf:rest Nc9f1912ba4fb4c3fa55f7d8dcffde1ad
60 N232adbb5994447c69ec0749f5bed0869 rdf:first sg:person.010555136403.19
61 rdf:rest Needab981cc5c4eb79917fb90a6c1a721
62 N3c3fefcadf304b5fab7d3732b13f2d6c schema:name Springer Nature
63 rdf:type schema:Organisation
64 N4453b41831394213b57b9fd88c9d5f97 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N44cb5790db4e4d538e8dafb3496468fa rdf:first N9c2a4a7e32dd473e81da81af3cf1a9c0
67 rdf:rest rdf:nil
68 N799c33a4c8ec4f209faa40d18fa469ef schema:name doi
69 schema:value 10.1007/978-3-319-62389-4_11
70 rdf:type schema:PropertyValue
71 N7e461cd30500444f8eab8035ef60eaa0 schema:isbn 978-3-319-62388-7
72 978-3-319-62389-4
73 schema:name Computing and Combinatorics
74 rdf:type schema:Book
75 N7fcfabf1a36a4468b1cf73ab0e49702d rdf:first sg:person.015654265661.98
76 rdf:rest N10dbe3409c11437a934aad762ae1a5f1
77 N865fbc4d76e5458abeb098e9aafa6bc9 schema:familyName Cao
78 schema:givenName Yixin
79 rdf:type schema:Person
80 N9a58441117454983b9a1f8b40ef386b9 rdf:first N865fbc4d76e5458abeb098e9aafa6bc9
81 rdf:rest N44cb5790db4e4d538e8dafb3496468fa
82 N9c2a4a7e32dd473e81da81af3cf1a9c0 schema:familyName Chen
83 schema:givenName Jianer
84 rdf:type schema:Person
85 Nc9f1912ba4fb4c3fa55f7d8dcffde1ad rdf:first sg:person.01105113721.52
86 rdf:rest N232adbb5994447c69ec0749f5bed0869
87 Ne10a083d1497413d96e5397fce93a968 schema:name dimensions_id
88 schema:value pub.1090448513
89 rdf:type schema:PropertyValue
90 Needab981cc5c4eb79917fb90a6c1a721 rdf:first sg:person.011747627223.07
91 rdf:rest rdf:nil
92 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
93 schema:name Mathematical Sciences
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:person.010555136403.19 schema:affiliation grid-institutes:grid.17089.37
99 schema:familyName Chen
100 schema:givenName Yong
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19
102 rdf:type schema:Person
103 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
104 schema:familyName Wang
105 schema:givenName Lusheng
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
107 rdf:type schema:Person
108 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
109 schema:familyName Lin
110 schema:givenName Guohui
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
112 rdf:type schema:Person
113 sg:person.011747627223.07 schema:affiliation grid-institutes:grid.35030.35
114 schema:familyName Wang
115 schema:givenName Dan
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011747627223.07
117 rdf:type schema:Person
118 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
119 schema:familyName Chen
120 schema:givenName Zhi-Zhong
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
122 rdf:type schema:Person
123 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
124 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
125 rdf:type schema:Organization
126 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong, China
127 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong, China
128 rdf:type schema:Organization
129 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
130 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
131 rdf:type schema:Organization
 




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


...