Ruchansky (Minimum Wiener Connector problem Wiener Index)

Time Complexity

$O(q(m*log(n)$+n*log^{2}(n)))

Space Complexity

$O(q(m+n*log(n)$)? words

(Keeps track of $O(qm)$ shortest-path distances and $O(q*log(n))$ approximate Steiner trees, each of size $O(n)$)

Approximate?

Approximate

Approximation Factor: O(1)

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2015

Reference

https://arxiv.org/abs/1504.00513