Graph problem-Need help

Revision en1, by freto, 2017-12-08 10:51:16

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?

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)