{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:49:51Z","timestamp":1765370991074,"version":"3.46.0"},"reference-count":27,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","funder":[{"name":"RISE Internal Research","award":["2021-01-006"],"award-info":[{"award-number":["2021-01-006"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>A spanning tree T of a connected graph G is an acyclic subgraph of G that connects all vertices of G with the minimum number of edges. Spanning tree enumeration is the problem of finding all distinct spanning trees of G and is a well-studied problem in graph theory with applications in various fields. In this paper, we propose an algorithm for enumerating spanning trees of k-trees that runs in [Formula: see text] time and takes [Formula: see text] space for a k-tree G having n vertices, m edges, and [Formula: see text] spanning trees. This is a substantial improvement in time complexity without increasing the space cost over the best spanning tree enumeration algorithm for general graphs which takes [Formula: see text] time and also requires [Formula: see text] space.<\/jats:p>","DOI":"10.1142\/s0129054125500054","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T04:20:13Z","timestamp":1745814013000},"page":"1173-1203","source":"Crossref","is-referenced-by-count":0,"title":["Efficiently Enumerating Spanning Trees of\n                    <i>k<\/i>\n                    -Trees"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2450-3377","authenticated-orcid":false,"given":"Muhammad Nur","family":"Yanhaona","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, BRAC University, Dhaka, Bangladesh"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6987-4855","authenticated-orcid":false,"given":"Rahnuma Islam","family":"Nishat","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Brock University, ON, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0112-0242","authenticated-orcid":false,"given":"Md. Saidur","family":"Rahman","sequence":"additional","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh"}]}],"member":"219","published-online":{"date-parts":[[2025,4,26]]},"reference":[{"key":"S0129054125500054BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/360336.360343"},{"key":"S0129054125500054BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90067-5"},{"key":"S0129054125500054BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1968.1082817"},{"key":"S0129054125500054BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3_12"},{"key":"S0129054125500054BIB005","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1956.5219803"},{"key":"S0129054125500054BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/0207024"},{"key":"S0129054125500054BIB007","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1958.tb03887.x"},{"key":"S0129054125500054BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1985.10011"},{"key":"S0129054125500054BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1964.1082276"},{"key":"S0129054125500054BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(61)90036-9"},{"key":"S0129054125500054BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/ICIEA.2006.257220"},{"key":"S0129054125500054BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979225030X"},{"key":"S0129054125500054BIB013","doi-asserted-by":"publisher","DOI":"10.7312\/kim-94412"},{"key":"S0129054125500054BIB014","doi-asserted-by":"crossref","unstructured":"T. Matsui, An algorithm for finding all the spanning trees in undirected graphs (1998).","DOI":"10.1007\/PL00009171"},{"key":"S0129054125500054BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1965.1082432"},{"key":"S0129054125500054BIB016","doi-asserted-by":"crossref","unstructured":"J. Ne\u0160et\u0159il and  P. O. De Mendez,  Structural Properties of Sparse Graphs, Building Bridges: Between Mathematics and Computer Science, eds.   M. Gr\u00f6tschel,  G. O. H. Katona and  G. S\u00e1gi  (Springer,  Berlin, Heidelberg,  2008), pp. 369\u2013426.","DOI":"10.1007\/978-3-540-85221-6_13"},{"key":"S0129054125500054BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90058-3"},{"key":"S0129054125500054BIB018","first-page":"1","volume-title":"XIth International Workshop on Symbolic and Numerical Methods, Modeling and Applications to Circuit Design","author":"Onete C. E.","year":"2010"},{"issue":"24","key":"S0129054125500054BIB019","first-page":"57","volume":"11","author":"Patil H.","year":"1986","journal-title":"Journal of Combinatorics, Information & System Sciences"},{"key":"S0129054125500054BIB020","doi-asserted-by":"publisher","DOI":"10.1109\/WCNC.1999.796997"},{"key":"S0129054125500054BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49475-3"},{"key":"S0129054125500054BIB022","doi-asserted-by":"publisher","DOI":"10.1080\/03772063.1981.11452333"},{"key":"S0129054125500054BIB023","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.3.237"},{"key":"S0129054125500054BIB024","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.38.331"},{"key":"S0129054125500054BIB025","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270881"},{"volume-title":"Introduction to Graph Theory","year":"1986","author":"Wilson R. J.","key":"S0129054125500054BIB026"},{"key":"S0129054125500054BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30448-4_26"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125500054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T09:07:31Z","timestamp":1765357651000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125500054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,26]]},"references-count":27,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1142\/S0129054125500054"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125500054","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2025,4,26]]}}}