2019/07/28 by Parikshit Saikia, Saikia, Parikshit, Sushanta Karmakar +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1907.12011
openalex publication_date 2019/07/28 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
The \Steiner tree problem is one of the fundamental and classical\nproblems in combinatorial optimization. In this paper, we study this problem in\nthe \CONGESTED \CLIQUE model of distributed computing and\npresent two deterministic distributed approximation algorithms for the same.\nThe first algorithm computes a Steiner tree in \O(n1/3) rounds and\n\O(n7/3) messages for a given connected undirected weighted graph\nof n nodes. Note here that \O(\⋅) notation hides polylogarithmic\nfactors in n. The second one computes a Steiner tree in O(S + \log\log n)\nrounds and O(S (n - t)2 + n2) messages, where S and t are the\n\shortest path diameter and the number of \terminal nodes\nrespectively in the given input graph. Both the algorithms admit an\napproximation factor of 2(1 - 1/\ℓ), where \ℓ is the number of terminal\nleaf nodes in the optimal Steiner tree. For graphs with S = \ω(n1/3\n\log n), the first algorithm exhibits better performance than the second one\nin terms of the round complexity. On the other hand, for graphs with S =\n\o(n1/3), the second algorithm outperforms the first one in terms of\nthe round complexity. In fact when S = O(\log\log n) then the second\nalgorithm admits a round complexity of O(\log\log n) and message complexity\nof \O(n2). To the best of our knowledge, this is the first work to\nstudy the Steiner tree problem in the \CONGESTED \CLIQUE\nmodel.\n