We are given a graph with n nodes.↵
↵
For every pair of nodes i,j (i!=j) there is an edge from i to j and an edge from j to i. Note that both these edges may have different cost.↵
↵
There is also a node S (source node). For every node i (i!=S) there is an edge from S to i. (No edge from i to S).↵
↵
A wheel tree is a tree which has several linear chains connected to S. (meaning that every node except S has atmost one child.)↵
↵
We are given an array D[i]. We have to construct a wheel tree from the given graph such that distance of ith node from S is <= D[i].↵
Distance is obviously the sum of edges.↵
↵
Each chain connected to S is called a "spoke".↵
↵
We have to remove some edges from the initial graph such that the distance conditions are satisfied ALSO we need to MINIMIZE the number of spokes.↵
↵
I think this might be a flow problem. But am not able to solve it.↵
↵
Any ideas?↵
↵
↵
EDIT: ↵
↵
contraints:↵
N is <=40.↵
↵
Any algorithm ( apart from brute :P )??↵
↵
↵
For every pair of nodes i,j (i!=j) there is an edge from i to j and an edge from j to i. Note that both these edges may have different cost.↵
↵
There is also a node S (source node). For every node i (i!=S) there is an edge from S to i. (No edge from i to S).↵
↵
A wheel tree is a tree which has several linear chains connected to S. (meaning that every node except S has atmost one child.)↵
↵
We are given an array D[i]. We have to construct a wheel tree from the given graph such that distance of ith node from S is <= D[i].↵
Distance is obviously the sum of edges.↵
↵
Each chain connected to S is called a "spoke".↵
↵
We have to remove some edges from the initial graph such that the distance conditions are satisfied ALSO we need to MINIMIZE the number of spokes.↵
↵
I think this might be a flow problem. But am not able to solve it.↵
↵
Any ideas?↵
↵
↵
EDIT: ↵
↵
contraints:↵
N is <=40.↵
↵
Any algorithm ( apart from brute :P )??↵
↵
