Finding a minimal tree-type network of a graph where each node is connected to each other and find the sum of each node to all the other nodes

Question

You were hired by a director of a small company with N employees to set up the network between the employees who have to send a weekly report to each of the other employees as a different part or their report is important for each employee, depending on the importance of their work they have to send a report Ki number of times per week

You have measured the time it takes for a message to be delivered between each 2 employees Due to budget cuts the network will only have N-1 connections between they employees and because of the simplicity of the technology you are using when one message is sent the entire network has to wait for it to be delivered (only 1 message at a time)

What you get is N -the number of employees, you get Ki which is the muber of times a report from worker i is to be sent per week, Tij which indicates the time a message traveles from employee i to employee j 1<=N<=13

0<=Ki<=10^3

0<=Tij<=10^3

Tij = Tji, Tii = 0

At first I assumed the most optimal network would be a star (tree) and all it would take is to determine which node to be in the center and since we were limited to an N at most 13 I decided to just brute force it and try them all, but that attempt failed as apparently this was not the most optimal network configuration (or so the test cases showed me) Then I thought maybe this would be solved by finding a minimum spanning tree or each full graph made from the employees, but since there are multiple minimum spanning trees and not all of them are equaly good for this problem that failed on paper already

I am currently a bit out of ideas, so a hint as to what direction I should be looking towards would be great

Answer 1

There are 13^11 ~ 1.8e12 spanning trees on 13 nodes, so brute force is out of the question. I believe that the intended solution is dynamic programming. For each pair comprised of a nonempty subset of nodes and a distinguished node belonging to the subset (the root), compute the optimal solution for a subproblem where the root represents all nodes outside of the subset as well as itself. The one-node sets are an obvious base case. For bigger subproblems, optimize using a dynamic subprogram over all partitions of the given set minus the root. The added cost on top of the combined sub-solutions is the cost of the links from the root to its children weighted by the number of communications that use those links.

Answer 2

In minimum spanning tree all the connections must form a connected tree. In this question we have no such restriction. So for each vertex i you could just connect it to a vertex j such that T(i,j) is minimum. This will guarantee that there are no cycles and every vertex will have at least 1 edge hence in total there will be less than N-1 edges, as is required.