{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T21:21:16Z","timestamp":1771104076214,"version":"3.50.1"},"reference-count":33,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p> Graph embedding is an important technique that maps a logical graph into a host graph, usually an interconnection network. In this paper, we compute the exact wirelength of embedding Christmas trees into trees. Moreover, we present an algorithm for embedding Christmas trees into caterpillars with dilation 3 proving that the lower bound obtained in [30] is sharp. Further, we solve the maximum subgraph problem for Christmas trees and provide a linear time algorithm to compute the exact wirelength of embedding Christmas trees into trees. <\/jats:p>","DOI":"10.1142\/s0129626415500085","type":"journal-article","created":{"date-parts":[[2015,12,31]],"date-time":"2015-12-31T02:13:35Z","timestamp":1451528015000},"page":"1550008","source":"Crossref","is-referenced-by-count":6,"title":["A Linear Time Algorithm for Embedding Christmas Trees into Certain Trees"],"prefix":"10.1142","volume":"25","author":[{"given":"Indra","family":"Rajasingh","sequence":"first","affiliation":[{"name":"School of Advanced Sciences, VIT University, Chennai 600 127, India"}]},{"given":"R. Sundara","family":"Rajan","sequence":"additional","affiliation":[{"name":"School of Advanced Sciences, VIT University, Chennai 600 127, India"}]},{"given":"Paul","family":"Manuel","sequence":"additional","affiliation":[{"name":"School of Advanced Sciences, VIT University, Chennai 600 127, India"}]}],"member":"219","published-online":{"date-parts":[[2015,12,30]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000089"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.09.003"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00098-5"},{"key":"p_6","first-page":"693","author":"Bezrukov S. L.","year":"1998","journal-title":"MFCS"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1013"},{"key":"p_8","first-page":"101","volume":"2","author":"Bezrukov S. L.","year":"2001","journal-title":"Nos."},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.05.026"},{"key":"p_10","first-page":"3763","volume":"40","author":"Lai P.-L.","year":"2010","journal-title":"Nos."},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.06.001"},{"key":"p_12","first-page":"559","volume":"14","author":"Yang X.","year":"2010","journal-title":"Nos."},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.12.010"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00227-2"},{"key":"p_15","first-page":"143","volume":"1","author":"Rottger M.","year":"2001","journal-title":"Nos."},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00161-4"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2008.10.040"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.09.051"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1002\/net.20027"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.09.013"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.4236\/am.2010.16065"},{"key":"p_23","first-page":"181","volume":"1","author":"Tsai C.-H.","year":"2008","journal-title":"Nos."},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(03)00037-6"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.12.001"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9443-x"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.07.003"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.006"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1080\/00207160.2012.697557"},{"key":"p_30","first-page":"1","volume":"1","author":"Manuel P.","year":"2012","journal-title":"Nos."},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.007"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00162-4"},{"key":"p_35","first-page":"55","volume":"1","author":"Hung C.-N.","year":"1999","journal-title":"Nos."},{"key":"p_36","doi-asserted-by":"publisher","DOI":"10.1007\/s000260050003"},{"key":"p_39","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxu031"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626415500085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:52:03Z","timestamp":1565200323000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626415500085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":33,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2015,12,30]]},"published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1142\/S0129626415500085"],"URL":"https:\/\/doi.org\/10.1142\/s0129626415500085","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}