{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T10:10:06Z","timestamp":1729246206986,"version":"3.27.0"},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T00:00:00Z","timestamp":1720828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"name":"NSERC Discovery"},{"name":"Brock University Startup"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,10,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Let $G$ be a vertex-weighted connected graph of $n$ vertices and let $T$ be a spanning tree of $G$. We call $T$ a maximum weighted internal spanning tree of $G$ if the sum of the weights of the internal vertices of $T$ is the maximum over all spanning trees of $G$. The maximum weighted internal spanning tree (MaxwIST) problem asks to find such a spanning tree $T$ of $G$. The problem is NP-hard. We give an $O(dn)$ time approximation algorithm for $d$-regular graphs of $n=|V|$ vertices that computes a spanning tree with total weight of the internal vertices is at least $\\frac{\\beta _{d}}{\\beta _{d} +d-2} - \\epsilon $ of the total weight of all the vertices of the graph for any $\\epsilon&amp;gt;0$, where $\\beta _{d} = (d-1)H_{d-1}$, and $H_{d-1} = \\sum _{i=1}^{d-1} i^{-1}$ is the $(d-1)$th harmonic number. For every $d \\geq 3$ and $n_{0} \\geq 1$, we show the construction of a $d$-regular graph of at least $n_{0}$ vertices, such that for any of its spanning trees, $\\frac{w(I)}{w(V)}\\le \\frac{d}{d+1}$ holds. We give an $O(dn)$ time approximation algorithm for subdivisions of $d$-regular graphs, where the ratio of the internal weight of the spanning tree with the total vertex weight of the graph is at least $\\frac{d-1}{2d-3} - \\epsilon $ for $\\epsilon&amp;gt;0$. We extend our study to $x$-subdivisions of Hamiltonian and hypoHamiltonian graphs, where each edge of the original Hamiltonian or hypoHamiltonian graph has been subdivided at least $x$ times. For those two graph classes, we show that there exists a spanning tree with internal vertex weight at least $1-\\frac{2}{x-1}$ of the total vertex weight of the graph. Furthermore, we give $O(n)$ time algorithm for $x$-subdivisions of biconnected outerplanar graphs and $4$-connected planar graphs to achieve the above bound.<\/jats:p>","DOI":"10.1093\/comjnl\/bxae055","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T06:33:35Z","timestamp":1718865215000},"page":"2898-2905","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for maximum weighted internal spanning trees in regular graphs and subdivisions of graphs"],"prefix":"10.1093","volume":"67","author":[{"given":"Sheikh Azizul","family":"Hakim","sequence":"first","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory , Department of Computer Science and Engineering, , Dhaka 1000 ,","place":["Bangladesh"]},{"name":"Bangladesh University of Engineering and Technology , Department of Computer Science and Engineering, , Dhaka 1000 ,","place":["Bangladesh"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahnuma Islam","family":"Nishat","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Brock University , Ontario L2S 3A1 ,","place":["Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Md Saidur","family":"Rahman","sequence":"additional","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory , Department of Computer Science and Engineering, , Dhaka 1000 ,","place":["Bangladesh"]},{"name":"Bangladesh University of Engineering and Technology , Department of Computer Science and Engineering, , Dhaka 1000 ,","place":["Bangladesh"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,7,13]]},"reference":[{"author":"Salamon","key":"2024101809311780800_ref1","article-title":"Degree-based spanning tree optimization"},{"key":"2024101809311780800_ref2","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/0020-0190(81)90141-1","article-title":"Constructing full spanning trees for cubic graphs","volume":"13","author":"Storer","journal-title":"Inf Process Lett"},{"key":"2024101809311780800_ref3","first-page":"260","article-title":"Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs","volume":"12635","author":"Biniaz","year":"2021","journal-title":"WALCOM"},{"key":"2024101809311780800_ref4","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s00453-011-9575-5","article-title":"Exact and parameterized algorithms for max internal spanning tree","volume":"65","author":"Binkele-Raible","journal-title":"Algorithmica"},{"key":"2024101809311780800_ref5","doi-asserted-by":"crossref","first-page":"4167","DOI":"10.1007\/s00453-018-00533-w","article-title":"Approximation algorithms for the maximum weight internal spanning tree problem","volume":"81","author":"Chen","journal-title":"Algorithmica"},{"key":"2024101809311780800_ref6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2012.03.004","article-title":"A linear vertex kernel for maximum internal spanning tree","volume":"79","author":"Fomin","journal-title":"J Comput Syst Sci"},{"key":"2024101809311780800_ref7","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1007\/s00453-013-9827-7","article-title":"Better approximation algorithms for the maximum internal spanning tree problem","volume":"71","author":"Knauer","journal-title":"Algorithmica"},{"journal-title":"WADS","article-title":"Either\/or: using vertex cover structure in designing FPT-algorithms - the case of k-internal spanning tree","author":"Prieto-Rodriguez","key":"2024101809311780800_ref8"},{"key":"2024101809311780800_ref9","first-page":"308","article-title":"Reducing to independent set structure \u2013 the case of k-internal spanning tree","volume":"12","author":"Prieto-Rodriguez","journal-title":"Nord J Comput"},{"volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey","key":"2024101809311780800_ref10"},{"key":"2024101809311780800_ref11","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","article-title":"On finding spanning trees with few leaves","volume":"105","author":"Salamon","journal-title":"Inf Process Lett"},{"key":"2024101809311780800_ref12","first-page":"467","article-title":"Approximating the maximum internal spanning tree problem via a maximum path-cycle cover","volume-title":"International Symposium on Algorithms and Computation","author":"Li"},{"key":"2024101809311780800_ref13","doi-asserted-by":"crossref","first-page":"5273","DOI":"10.1016\/j.tcs.2009.08.029","article-title":"Approximating the maximum internal spanning tree problem","volume":"410","author":"Salamon","journal-title":"Theor Comput Sci"},{"author":"Nishizeki","key":"2024101809311780800_ref14","article-title":"Planar Graph Drawing"},{"volume-title":"Basic Graph Theory Undergraduate Topics in Computer Science","author":"Rahman","key":"2024101809311780800_ref15"},{"article-title":"Planar graphs: theory and algorithms","volume-title":"Annals of Discrete Mathematics","author":"Nishizeki","key":"2024101809311780800_ref16"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/10\/2898\/59729552\/bxae055.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/10\/2898\/59729552\/bxae055.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T09:31:38Z","timestamp":1729243898000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/10\/2898\/7713287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,13]]},"references-count":16,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2024,7,13]]},"published-print":{"date-parts":[[2024,10,12]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxae055","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2024,10]]},"published":{"date-parts":[[2024,7,13]]}}}