Given two vertex sets $V_1$ and $V_2$. The vertices in $V_2$ have a limitation on the maximum degree of each vertex being $K$. I need to find an allocation algorithm such that every pair of vertices in $V_1$ is interconnected via a vertex in $V_2$ i.e $X \leftrightarrow Y \leftrightarrow Z$ , where $X,Z \in V_1$ and $Y \in V_2$.

The goal is to find an allocation that minimizes the distances between all such pairs in $V_1$. The distance is measured as : $\; dist(X, Y) + dist(Y, Z)\;$. The distances are provided beforehand. I kind of came up with an algorithm, but it doesn't guarantee optimality. Any help will be appreciated.

  • 1
    $\begingroup$ Say exactly what you want to minimize. The largest distance? The average distance? $\endgroup$ – Brendan McKay Mar 15 at 7:29
  • $\begingroup$ The total of all shortest distances between all pairs of vertices from set V1 $\endgroup$ – Aizen Mar 15 at 14:12
  • $\begingroup$ This problem isn't clearly written out OP. It is very hard to follow your question. $\endgroup$ – Mike Mar 19 at 15:43
  • $\begingroup$ @Mike can you point out which part was unclear. I added an image, but for some reason it's not there in the question anymore. $\endgroup$ – Aizen Mar 20 at 17:32
  • $\begingroup$ @Mike here is the link math.stackexchange.com/questions/3145081/… $\endgroup$ – Aizen Mar 20 at 17:33

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.