2
$\begingroup$

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)$.

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

0

Reset to default

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.