{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,20]],"date-time":"2022-11-20T23:26:15Z","timestamp":1668986775146},"reference-count":25,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p> For a connected labeled graph [Formula: see text], a spanning tree [Formula: see text] is a connected and acyclic subgraph that spans all vertices of [Formula: see text]. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of [Formula: see text]. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of [Formula: see text] processors for parallel algorithmics, where [Formula: see text] and [Formula: see text] are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s1793830918500052","type":"journal-article","created":{"date-parts":[[2017,11,14]],"date-time":"2017-11-14T01:21:46Z","timestamp":1510622506000},"page":"1850005","source":"Crossref","is-referenced-by-count":1,"title":["Listing all spanning trees in Halin graphs \u2014 sequential and Parallel view"],"prefix":"10.1142","volume":"10","author":[{"given":"K. Krishna Mohan","family":"Reddy","sequence":"first","affiliation":[{"name":"Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Renjith","sequence":"additional","affiliation":[{"name":"Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Sadagopan","sequence":"additional","affiliation":[{"name":"Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,2,14]]},"reference":[{"key":"S1793830918500052BIB001","first-page":"376","volume":"23","author":"Cayley A.","year":"1889","journal-title":"Quart. J. Pure Appl. Math."},{"key":"S1793830918500052BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.037"},{"key":"S1793830918500052BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.04.019"},{"key":"S1793830918500052BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497291"},{"key":"S1793830918500052BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.07.007"},{"key":"S1793830918500052BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/0207024"},{"key":"S1793830918500052BIB008","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"S1793830918500052BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"S1793830918500052BIB010","volume-title":"An Introduction to Parallel Algorithms","author":"JaJa J.","year":"1992"},{"key":"S1793830918500052BIB011","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979225030X"},{"key":"S1793830918500052BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010008"},{"key":"S1793830918500052BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979427087X"},{"key":"S1793830918500052BIB014","first-page":"95","volume":"29","author":"Lou D.","year":"2004","journal-title":"Austral. J. Combin."},{"key":"S1793830918500052BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009171"},{"key":"S1793830918500052BIB016","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120217"},{"key":"S1793830918500052BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1965.1082385"},{"key":"S1793830918500052BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00240-5"},{"key":"S1793830918500052BIB019","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.3.237"},{"key":"S1793830918500052BIB020","first-page":"331","volume":"38","author":"Shioura A.","year":"1993","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"S1793830918500052BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0071635"},{"key":"S1793830918500052BIB022","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"S1793830918500052BIB023","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"S1793830918500052BIB024","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"S1793830918500052BIB025","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"2003","edition":"2"},{"key":"S1793830918500052BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.017"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830918500052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:11:35Z","timestamp":1565111495000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830918500052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":25,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2018,2,14]]},"published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.1142\/S1793830918500052"],"URL":"https:\/\/doi.org\/10.1142\/s1793830918500052","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}