Graph problem-Need help
Difference between en1 and en2, changed 86 character(s)
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 )??↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English freto 2017-12-08 11:21:02 86
en1 English freto 2017-12-08 10:51:16 911 Initial revision (published)