An Approximation Algorithm for Maximum Internal Spanning Tree

Ontology type: schema:Chapter      Open Access: True

Chapter Info

DATE

2017-02-21

AUTHORS ABSTRACT

Given a graph G, the maximum internal spanning tree problem (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{3}{4}$$\end{document}. In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{13}{17}$$\end{document}) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. As our recent \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{2}$$\end{document}-approximation algorithm for the weighted version of the problem shows, the discovered structure may be used to design better algorithms for related problems. More... »

PAGES

385-396

Book

TITLE

WALCOM: Algorithms and Computation

ISBN

978-3-319-53924-9
978-3-319-53925-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-53925-6_30

DOI

http://dx.doi.org/10.1007/978-3-319-53925-6_30

DIMENSIONS

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

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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"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"
}
],
"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": "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"
},
"givenName": "Youta",
"id": "sg:person.011526465541.54",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011526465541.54"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of Computer Science and Technology, Tianjin University, No. 135, Yaguan Road, Tianjin, China",
"id": "http://www.grid.ac/institutes/grid.33763.32",
"name": [
"School of Computer Science and Technology, Tianjin University, No. 135, Yaguan Road, Tianjin, China"
],
"type": "Organization"
},
"familyName": "Guo",
"givenName": "Fei",
"id": "sg:person.0776100512.16",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0776100512.16"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
],
"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"
}
],
"datePublished": "2017-02-21",
"datePublishedReg": "2017-02-21",
"description": "Given a graph G, the maximum internal spanning tree problem (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of \\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}$$\\frac{3}{4}$$\\end{document}. In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, \\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}$$\\frac{13}{17}$$\\end{document}) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. As our recent \\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}$$\\frac{1}{2}$$\\end{document}-approximation algorithm for the weighted version of the problem shows, the discovered structure may be used to design better algorithms for related problems.",
"editor": [
{
"familyName": "Poon",
"givenName": "Sheung-Hung",
"type": "Person"
},
{
"familyName": "Rahman",
"givenName": "Md. Saidur",
"type": "Person"
},
{
"familyName": "Yen",
"givenName": "Hsu-Chun",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-53925-6_30",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-53924-9",
"978-3-319-53925-6"
],
"name": "WALCOM: Algorithms and Computation",
"type": "Book"
},
"keywords": [
"polynomial-time approximation algorithm",
"same time complexity",
"approximation algorithm",
"time complexity",
"best polynomial-time approximation algorithm",
"spanning tree problem",
"best algorithm",
"communication networks",
"new approximation algorithm",
"algorithm",
"new algorithm",
"tree problem",
"spanning tree",
"supply network",
"simple algorithm",
"network",
"Maximum Internal Spanning Tree",
"weighted version",
"complexity",
"related problems",
"water supply network",
"NPs",
"graph G",
"tree T",
"possible applications",
"deep structure",
"applications",
"Maximum Internal Spanning Tree problem",
"vertices",
"trees",
"version",
"design",
"number",
"internal vertices",
"best ratio",
"problem",
"literature",
"structure",
"mist",
"same ratio",
"ratio",
"paper"
],
"name": "An Approximation Algorithm for Maximum Internal Spanning Tree",
"pagination": "385-396",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1083898580"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-53925-6_30"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-53925-6_30",
"https://app.dimensions.ai/details/publication/pub.1083898580"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:43",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_185.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-53925-6_30"
}
]

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-53925-6_30'

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-53925-6_30'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-53925-6_30'

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-53925-6_30'

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

139 TRIPLES      23 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N388877aa28114e2384de8b4d52f65584
4 schema:datePublished 2017-02-21
5 schema:datePublishedReg 2017-02-21
6 schema:description Given a graph G, the maximum internal spanning tree problem (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{3}{4}$$\end{document}. In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{13}{17}$$\end{document}) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. As our recent \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{2}$$\end{document}-approximation algorithm for the weighted version of the problem shows, the discovered structure may be used to design better algorithms for related problems.
7 schema:editor Nc07fd8a2033049f7b3106b326b148dd2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N1bea6dee84c9405ca3c2a8d0d4e68f58
12 schema:keywords Maximum Internal Spanning Tree
13 Maximum Internal Spanning Tree problem
14 NPs
15 algorithm
16 applications
17 approximation algorithm
18 best algorithm
19 best polynomial-time approximation algorithm
20 best ratio
21 communication networks
22 complexity
23 deep structure
24 design
25 graph G
26 internal vertices
27 literature
28 mist
29 network
30 new algorithm
31 new approximation algorithm
32 number
33 paper
34 polynomial-time approximation algorithm
35 possible applications
36 problem
37 ratio
38 related problems
39 same ratio
40 same time complexity
41 simple algorithm
42 spanning tree
43 spanning tree problem
44 structure
45 supply network
46 time complexity
47 tree T
48 tree problem
49 trees
50 version
51 vertices
52 water supply network
53 weighted version
54 schema:name An Approximation Algorithm for Maximum Internal Spanning Tree
55 schema:pagination 385-396
56 schema:productId N17067cd386974d729f3855282e49e423
57 N1af51519014b451f921e3036ce486c82
58 schema:publisher N77b5310de34e495da255b5e0338d6ab8
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083898580
60 https://doi.org/10.1007/978-3-319-53925-6_30
61 schema:sdDatePublished 2022-05-20T07:43
63 schema:sdPublisher Ncfd732aa3f6344a591ace80f397daed0
64 schema:url https://doi.org/10.1007/978-3-319-53925-6_30
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N17067cd386974d729f3855282e49e423 schema:name doi
69 schema:value 10.1007/978-3-319-53925-6_30
70 rdf:type schema:PropertyValue
71 N1af51519014b451f921e3036ce486c82 schema:name dimensions_id
72 schema:value pub.1083898580
73 rdf:type schema:PropertyValue
74 N1bea6dee84c9405ca3c2a8d0d4e68f58 schema:isbn 978-3-319-53924-9
75 978-3-319-53925-6
76 schema:name WALCOM: Algorithms and Computation
77 rdf:type schema:Book
78 N2af428875fa84877872ee032dc89a9b9 schema:familyName Yen
79 schema:givenName Hsu-Chun
80 rdf:type schema:Person
81 N388877aa28114e2384de8b4d52f65584 rdf:first sg:person.015654265661.98
82 rdf:rest N8283b213bd514032bf259d95e6625357
83 N73c6e46695f64b10b0c1cee309d85cae schema:familyName Rahman
84 schema:givenName Md. Saidur
85 rdf:type schema:Person
86 N77b5310de34e495da255b5e0338d6ab8 schema:name Springer Nature
87 rdf:type schema:Organisation
88 N8283b213bd514032bf259d95e6625357 rdf:first sg:person.011526465541.54
89 rdf:rest Nb2f3fdd8fa5f4709968110d12d64f5c7
90 N8c87d88ec5ea4846863342ee3d8494d2 rdf:first sg:person.01105113721.52
91 rdf:rest rdf:nil
92 N8d1f6eda7cb34a4799bbea030f8cb5ed rdf:first N2af428875fa84877872ee032dc89a9b9
93 rdf:rest rdf:nil
94 Nb2f3fdd8fa5f4709968110d12d64f5c7 rdf:first sg:person.0776100512.16
95 rdf:rest N8c87d88ec5ea4846863342ee3d8494d2
96 Nb4f6ce15fa5547b28061f99a7e15663b schema:familyName Poon
97 schema:givenName Sheung-Hung
98 rdf:type schema:Person
99 Nc07fd8a2033049f7b3106b326b148dd2 rdf:first Nb4f6ce15fa5547b28061f99a7e15663b
100 rdf:rest Nde0f6069fed74b53bd21ddf775c695c4
101 Ncfd732aa3f6344a591ace80f397daed0 schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 Nde0f6069fed74b53bd21ddf775c695c4 rdf:first N73c6e46695f64b10b0c1cee309d85cae
104 rdf:rest N8d1f6eda7cb34a4799bbea030f8cb5ed
105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information and Computing Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
109 schema:name Computation Theory and Mathematics
110 rdf:type schema:DefinedTerm
111 sg:person.01105113721.52 schema:affiliation grid-institutes:None
112 schema:familyName Wang
113 schema:givenName Lusheng
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
115 rdf:type schema:Person
116 sg:person.011526465541.54 schema:affiliation grid-institutes:grid.412773.4
118 schema:givenName Youta
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011526465541.54
120 rdf:type schema:Person
121 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
122 schema:familyName Chen
123 schema:givenName Zhi-Zhong
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
125 rdf:type schema:Person
126 sg:person.0776100512.16 schema:affiliation grid-institutes:grid.33763.32
127 schema:familyName Guo
128 schema:givenName Fei
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0776100512.16
130 rdf:type schema:Person
131 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
132 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
133 rdf:type schema:Organization
134 grid-institutes:grid.33763.32 schema:alternateName School of Computer Science and Technology, Tianjin University, No. 135, Yaguan Road, Tianjin, China
135 schema:name School of Computer Science and Technology, Tianjin University, No. 135, Yaguan Road, Tianjin, China
136 rdf:type schema:Organization
137 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
138 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
139 rdf:type schema:Organization