Is there an algorithm with runtime $\mathcal{O}(n^2)$ that for given weighted graph $G$, partition it into 2 cluster $C_1,C_2$ such that sum of diameters of two clusters minimized?

I find a paper with title

"C. Monma and S. Suri, Partitioning points and graphs to minimize the maximum or the sum of diameters"

in some related papers but i can't access to above paper to find out their's algorithm. The above paper solve my problem in $O(n^2)$.

  • $\begingroup$ This is another paper; however with loose bounds. $\endgroup$ Sep 2, 2021 at 21:20
  • $\begingroup$ Thanks. But the running time of the algorithm is not $O(n^2)$. $\endgroup$ Sep 2, 2021 at 21:43
  • $\begingroup$ @Dmitry How it can be related to my problem? $\endgroup$ Sep 2, 2021 at 21:52
  • $\begingroup$ @nirshahar The graph is weighted. $\endgroup$ Sep 3, 2021 at 9:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.