Approximation algorithms for the optimal \(p\)-source communication spanning tree (Q1887037)

Given an undirected graph \(G=(V,E)\) with nonnegative edge weights \(w\) and a set \(S \subseteq V\) of \(p\) sources, the optimal \(p\)-source communication spanning tree problem (\(p\)-OCT) is to find a spanning tree \(T\) of \(G\) minimising \(\sum_{s \in S} \sum_{v \in V} d_{T,w}(s,v)\). This problem is NP-complete for fixed \(p \geq 2\), even if \(w\) fulfils the triangle inequality. \(2\)-OCT can be 3-approximated in \(O(m+n\log n)\) time, and \(p\)-OCT can be 2-approximated in \(O(n^{p-1})\) time if \(w\) fulfils the triangle inequality. For a survey of related results see [\textit{B. Y. Wu} and \textit{K.-M. Chao}, Spanning trees and optimization problems (Discrete Mathematics and its Applications. Boca Raton, FL: Chapman and Hall/CRC) (2004; Zbl 1072.90047)].