{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T22:46:20Z","timestamp":1754261180957,"version":"3.40.5"},"reference-count":38,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:p> The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGESTED CLIQUE model (CCM) [29] of distributed computing. For the Steiner tree problem in the CCM, we consider that each vertex of the input graph is uniquely mapped to a processor and edges are naturally mapped to the links between the corresponding processors. Regarding output, each processor should know whether the vertex assigned to it is in the solution or not and which of its incident edges are in the solution. We present two deterministic distributed approximation algorithms for the Steiner tree problem in the CCM. The first algorithm computes a Steiner tree using [Formula: see text] rounds and [Formula: see text] messages for a given connected undirected weighted graph of [Formula: see text] nodes. Note here that [Formula: see text] notation hides polylogarithmic factors in [Formula: see text]. The second one computes a Steiner tree using [Formula: see text] rounds and [Formula: see text] messages, where [Formula: see text] and [Formula: see text] are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of [Formula: see text], where [Formula: see text] is the number of leaf nodes in the optimal Steiner tree. For graphs with [Formula: see text], the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with [Formula: see text], the second algorithm outperforms the first one in terms of the round complexity. In fact when [Formula: see text] then the second algorithm achieves a round complexity of [Formula: see text] and message complexity of [Formula: see text]. To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM. <\/jats:p>","DOI":"10.1142\/s0129054120500367","type":"journal-article","created":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T10:36:48Z","timestamp":1604918208000},"page":"941-968","source":"Crossref","is-referenced-by-count":7,"title":["Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6306-9994","authenticated-orcid":false,"given":"Parikshit","family":"Saikia","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology, Guwahati, India, 781039, India"}]},{"given":"Sushanta","family":"Karmakar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology, Guwahati, India, 781039, India"}]}],"member":"219","published-online":{"date-parts":[[2020,11,10]]},"reference":[{"key":"S0129054120500367BIB001","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/978-3-642-31585-5_39","volume-title":"Proc. 39th Int. Colloquium on Automata, Languages, and Programming, ICALP\u201912","author":"Berns A.","year":"2012"},{"key":"S0129054120500367BIB002","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/1806689.1806769","volume-title":"Proc. Forty-second ACM Symposium on Theory of Computing, STOC \u201910","author":"Byrka J.","year":"2010"},{"key":"S0129054120500367BIB003","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/3293611.3331633","volume-title":"Proc. 2019 ACM Symposium on Principles of Distributed Computing, PODC \u201919","author":"Censor-Hillel K.","year":"2019"},{"key":"S0129054120500367BIB004","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/2767386.2767414","volume-title":"Proc. 2015 ACM Symposium on Principles of Distributed Computing, PODC \u201915","author":"Censor-Hillel K.","year":"2015"},{"key":"S0129054120500367BIB005","first-page":"380","volume-title":"Proc. 11th Ann. Int. Conf. Computing and Combinatorics, COCOON \u201905","author":"Chalermsook P.","year":"2005"},{"issue":"1","key":"S0129054120500367BIB006","first-page":"73","volume":"74","author":"Chen G.-H.","year":"1993","journal-title":"Inform. Sci."},{"issue":"3","key":"S0129054120500367BIB007","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"Chleb\u00edk M.","year":"2008","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"S0129054120500367BIB008","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"Dean J.","year":"2008","journal-title":"Commun. ACM"},{"key":"S0129054120500367BIB009","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-642-33651-5_14","volume-title":"Proc. 26th Int. Conf. Distributed Computing, DISC \u201912","author":"Dolev D.","year":"2012"},{"key":"S0129054120500367BIB010","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/2332432.2332443","volume-title":"Proc. 2012 ACM Symposium on Principles of Distributed Computing, PODC \u201912","author":"Drucker A.","year":"2012"},{"key":"S0129054120500367BIB011","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1145\/2611462.2611493","volume-title":"Proc. 2014 ACM Symposium on Principles of Distributed Computing, PODC \u201914","author":"Drucker A.","year":"2014"},{"key":"S0129054120500367BIB012","first-page":"129","volume-title":"Proc. 12th Ann. Symp. Switching and Automata Theory, SWAT \u201971","author":"Fischer M. J.","year":"1971"},{"issue":"3","key":"S0129054120500367BIB013","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1007\/s00453-012-9690-y","volume":"68","author":"Gehweiler J.","year":"2014","journal-title":"Algorithmica"},{"key":"S0129054120500367BIB014","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2933057.2933103","volume-title":"Proc. 2016 ACM Symposium on Principles of Distributed Computing, PODC \u201916","author":"Ghaffari M.","year":"2016"},{"key":"S0129054120500367BIB016","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/2767386.2767434","volume-title":"Proc. 2015 ACM Symposium on Principles of Distributed Computing, PODC \u201915","author":"Hegeman J. W.","year":"2015"},{"issue":"3","key":"S0129054120500367BIB017","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.tcs.2015.09.029","volume":"608","author":"Hegeman J. W.","year":"2015","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120500367BIB018","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/978-3-662-45174-8_35","volume-title":"Proc. 28th Int. Conf. Distributed Computing, DISC\u201914","author":"Hegeman J. W.","year":"2014"},{"key":"S0129054120500367BIB019","first-page":"1","volume-title":"19th Int. Conf. Principles of Distributed Systems, OPODIS \u201915","author":"Holzer S.","year":"2015"},{"key":"S0129054120500367BIB020","first-page":"2620","volume-title":"Proc. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201918","author":"Jurdzi\u0144ski T.","year":"2018"},{"key":"S0129054120500367BIB021","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proc. Symp. Complexity of Computer Computations","author":"Karp R. M.","year":"1972"},{"key":"S0129054120500367BIB022","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/1400751.1400787","volume-title":"Proc. Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC \u201908","author":"Khan M.","year":"2008"},{"issue":"6","key":"S0129054120500367BIB023","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"Khan M.","year":"2008","journal-title":"Distributed Comput."},{"key":"S0129054120500367BIB024","first-page":"391","volume-title":"Proc. Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201915","author":"Klauck H.","year":"2015"},{"issue":"2","key":"S0129054120500367BIB025","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"Kou L.","year":"1981","journal-title":"Acta Informatica"},{"key":"S0129054120500367BIB026","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/2484239.2501983","volume-title":"Proc. 2013 ACM Symposium on Principles of Distributed Computing, PODC \u201913","author":"Lenzen C.","year":"2013"},{"key":"S0129054120500367BIB027","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/2767386.2767398","volume-title":"Proc. 2015 ACM Symposium on Principles of Distributed Computing, PODC \u201915","author":"Lenzen C.","year":"2015"},{"issue":"1","key":"S0129054120500367BIB028","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"Linial N.","year":"1992","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S0129054120500367BIB029","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Lotker Z.","year":"2005","journal-title":"SIAM J. Comput."},{"issue":"2","key":"S0129054120500367BIB030","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"Munro I.","year":"1971","journal-title":"Inform. Process. Lett."},{"key":"S0129054120500367BIB031","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1145\/2591796.2591850","volume-title":"Proc. Forty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201914","author":"Nanongkai D.","year":"2014"},{"key":"S0129054120500367BIB032","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1145\/3293611.3331569","volume-title":"Proc. 2019 ACM Symposium on Principles of Distributed Computing, PODC \u201919","author":"Pai S.","year":"2019"},{"key":"S0129054120500367BIB033","first-page":"1","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"Patt-Shamir B.","year":"2017"},{"key":"S0129054120500367BIB034","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1145\/1993806.1993851","volume-title":"Proc. 30th Ann. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC \u201911","author":"Patt-Shamir B.","year":"2011"},{"journal-title":"SIAM: Discr. Math. Appl.","year":"2000","author":"Peleg D.","key":"S0129054120500367BIB035"},{"issue":"5","key":"S0129054120500367BIB036","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"Peleg D.","year":"2000","journal-title":"SIAM J. Comput."},{"key":"S0129054120500367BIB037","first-page":"47:1","volume-title":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)","author":"Pemmaraju S. V.","year":"2016"},{"key":"S0129054120500367BIB038","first-page":"41","volume-title":"Proc. 20th Int. Conf. Distributed Computing and Networking, ICDCN \u201919","author":"Saikia P.","year":"2019"},{"issue":"2","key":"S0129054120500367BIB039","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"Wu Y. F.","year":"1986","journal-title":"Acta Informatica"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T10:13:52Z","timestamp":1608113632000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":38,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["10.1142\/S0129054120500367"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500367","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,11]]}}}