CODEWITHSUNDEEP
algorithm
user644248
user644248

Reputation: 29

A algorithm problem

I want to design a algorithm. In a directed graph G=（V,E）, and each arc has a numerical weight. The algorithm needs to return a set S of arcs of maximum weight so that no two arcs in A have the same tail. Assume that it has at least 7 nodes and 10 arcs. Could anyone give some hints about this algorithm?

Upvotes: 2

Views: 187

Answers (1)

phimuemue
phimuemue

Reputation: 36051

You say that your arcs are not allowed to have the same tail. So I would divide the set of arcs into several "bins" which are determined by the tail of the arc. I.e. you take each arc, look at its tail, and put it into the corresponding bin.

Consider the graph consistign of the following arcs:

(1->2)
(1->3)
(2->1)
(2->4)
(3->2)

Then, we have something as follows:

bin          1    |    2   |  3   | 4 
arc        2   3  | 1    4 |  2   | (empty)
weight     ..  .. | ..  .. | ..   |

It is now clear, that we can take at most one arc from each bin. In order to maximize the sum, we can pick always the one with the largest weight in each bin.

Edit: Note that your algorithm does not need to do this whole bin-thing. It can just walk across all arcs and update the solution dynamically.

Upvotes: 2

Related Questions