{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T14:04:52Z","timestamp":1726063492481},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030369866"},{"type":"electronic","value":"9783030369873"}],"license":[{"start":{"date-parts":[[2019,12,9]],"date-time":"2019-12-09T00:00:00Z","timestamp":1575849600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-36987-3_7","type":"book-chapter","created":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T05:34:36Z","timestamp":1577856876000},"page":"111-126","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Round-Message Trade-Off in Distributed Steiner Tree Construction in the CONGEST Model"],"prefix":"10.1007","author":[{"given":"Parikshit","family":"Saikia","sequence":"first","affiliation":[]},{"given":"Sushanta","family":"Karmakar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,9]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","unstructured":"Bacrach, N., Censor-Hillel, K., Dory, M., Efron, Y., Leitersdorf, D., Paz, A.: Hardness of distributed optimization. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, pp. 238\u2013247 (2019). \nhttps:\/\/doi.org\/10.1145\/3293611.3331597","DOI":"10.1145\/3293611.3331597"},{"issue":"2","key":"7_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/90.490746","volume":"4","author":"F Bauer","year":"1996","unstructured":"Bauer, F., Varma, A.: Distributed algorithms for multicast path setup in data networks. IEEE\/ACM Trans. Netw. 4(2), 181\u2013191 (1996). \nhttps:\/\/doi.org\/10.1109\/90.490746","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"7_CR3","doi-asserted-by":"publisher","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: An improved LP-based approximation for Steiner tree. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 583\u2013592 (2010). \nhttps:\/\/doi.org\/10.1145\/1806689.1806769","DOI":"10.1145\/1806689.1806769"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/11533719_39","volume-title":"Computing and Combinatorics","author":"P Chalermsook","year":"2005","unstructured":"Chalermsook, P., Fakcharoenphol, J.: Simple distributed algorithms for approximating minimum Steiner trees. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 380\u2013389. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/11533719_39"},{"issue":"1\u20132","key":"7_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0255(93)90128-9","volume":"74","author":"GH Chen","year":"1993","unstructured":"Chen, G.H., Houle, M.E., Kuo, M.T.: The Steiner problem in distributed computing systems. Inf. Sci. 74(1\u20132), 73\u201396 (1993). \nhttps:\/\/doi.org\/10.1016\/0020-0255(93)90128-9","journal-title":"Inf. Sci."},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: inapproximability results. Theoret. Comput. Sci. 406(3), 207\u2013214 (2008). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2008.06.046","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986). \nhttps:\/\/doi.org\/10.1016\/S0019-9958(86)80023-7","journal-title":"Inf. Control"},{"key":"7_CR8","doi-asserted-by":"publisher","unstructured":"Das Sarma, A., et al.: Distributed verification and hardness of distributed approximation. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 363\u2013372 (2011). \nhttps:\/\/doi.org\/10.1145\/1993636.1993686","DOI":"10.1145\/1993636.1993686"},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Elkin, M.: A simple deterministic distributed MST algorithm, with near-optimal time and message complexities. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, pp. 157\u2013163 (2017). \nhttps:\/\/doi.org\/10.1145\/3087801.3087823","DOI":"10.1145\/3087801.3087823"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"1","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 1, 66\u201377 (1983). \nhttps:\/\/doi.org\/10.1145\/357195.357200","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"7_CR11","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"JA Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302\u2013316 (1998). \nhttps:\/\/doi.org\/10.1137\/S0097539794261118","journal-title":"SIAM J. Comput."},{"key":"7_CR12","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Hershkowitz, D.E., Wajc, D.: Round- and message-optimal distributed graph algorithms. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pp. 119\u2013128 (2018). \nhttps:\/\/doi.org\/10.1145\/3212734.3212737","DOI":"10.1145\/3212734.3212737"},{"key":"7_CR13","unstructured":"Hauptmann, M., Karpinski, M.: A Compendium on Steiner Tree Problems (2015). \nhttp:\/\/theory.cs.uni-bonn.de\/info5\/steinerkompendium\/netcompendium.html"},{"key":"7_CR14","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston (1972). \nhttps:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"7_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.: New approximation algorithms for the Steiner tree problems. J. Comb. Optim. 1(1), 47\u201365 (1997). \nhttps:\/\/doi.org\/10.1023\/A:1009758919736","journal-title":"J. Comb. Optim."},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. In: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 263\u2013272 (2008). \nhttps:\/\/doi.org\/10.1145\/1400751.1400787","DOI":"10.1145\/1400751.1400787"},{"issue":"6","key":"7_CR17","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"M Khan","year":"2008","unstructured":"Khan, M., Pandurangan, G.: A fast distributed approximation algorithm for minimum spanning trees. Distrib. Comput. 20(6), 391\u2013402 (2008). \nhttps:\/\/doi.org\/10.1007\/s00446-007-0047-8","journal-title":"Distrib. Comput."},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L Kou","year":"1981","unstructured":"Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica 15(2), 141\u2013145 (1981). \nhttps:\/\/doi.org\/10.1007\/BF00288961","journal-title":"Acta Informatica"},{"issue":"1","key":"7_CR19","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7:1\u20137:27 (2015). \nhttps:\/\/doi.org\/10.1145\/2699440","journal-title":"J. ACM"},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40\u201366 (1998). \nhttps:\/\/doi.org\/10.1006\/jagm.1998.0929","journal-title":"J. Algorithms"},{"key":"7_CR21","doi-asserted-by":"publisher","unstructured":"Lenzen, C., Patt-Shamir, B.: Improved distributed Steiner forest construction. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2014, pp. 262\u2013271 (2014). \nhttps:\/\/doi.org\/10.1145\/2611462.2611464","DOI":"10.1145\/2611462.2611464"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pp. 153\u2013162 (2015). \nhttps:\/\/doi.org\/10.1145\/2767386.2767398","DOI":"10.1145\/2767386.2767398"},{"key":"7_CR23","doi-asserted-by":"publisher","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 743\u2013756 (2017). \nhttps:\/\/doi.org\/10.1145\/3055399.3055449","DOI":"10.1145\/3055399.3055449"},{"key":"7_CR24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Discrete Math. Appl. (2000). \nhttps:\/\/doi.org\/10.1137\/1.9780898719772","journal-title":"SIAM Discrete Math. Appl."},{"issue":"1","key":"7_CR25","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"HJ Promel","year":"2000","unstructured":"Promel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio 5\/3. J. Algorithms 36(1), 89\u2013101 (2000). \nhttps:\/\/doi.org\/10.1006\/jagm.2000.1086","journal-title":"J. Algorithms"},{"key":"7_CR26","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 770\u2013779 (2000)"},{"key":"7_CR27","doi-asserted-by":"publisher","unstructured":"Saikia, P., Karmakar, S.: A simple $$2(1-1\/\\ell )$$ factor distributed approximation algorithm for Steiner tree in the congest model. In: Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN 2019, pp. 41\u201350 (2019). \nhttps:\/\/doi.org\/10.1145\/3288599.3288629","DOI":"10.1145\/3288599.3288629"},{"key":"7_CR28","first-page":"573","volume":"24","author":"H Takahashi","year":"1980","unstructured":"Takahashi, H., Matasuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Japan 24, 573\u2013577 (1980)","journal-title":"Math. Japan"},{"issue":"2","key":"7_CR29","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"YF Wu","year":"1986","unstructured":"Wu, Y.F., Widmayer, P., Wong, C.K.: A faster approximation algorithm for the Steiner problem in graphs. Acta Informatica 23(2), 223\u2013229 (1986). \nhttps:\/\/doi.org\/10.1007\/BF00289500","journal-title":"Acta Informatica"},{"issue":"5","key":"7_CR30","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5), 463\u2013470 (1993). \nhttps:\/\/doi.org\/10.1007\/BF01187035","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing and Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-36987-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T05:35:37Z","timestamp":1577856937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-36987-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,9]]},"ISBN":["9783030369866","9783030369873"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-36987-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019,12,9]]},"assertion":[{"value":"9 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICDCIT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Distributed Computing and Internet Technology","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bhubaneswar","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 January 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 January 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"icdcit0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.icdcit.ac.in\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"110","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"18% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"In addition, there are 6 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}