Algorithm problem

Question

I want to develop an algorithm. In the directed graph, G = (V, E), and each arc has a numerical weight. The algorithm should return the set S of arcs of maximum weight, so that none of the two arcs in has the same tail. Suppose that it has at least 7 nodes and 10 arcs. Can anyone give any hints of this algorithm?

Answer 1

You say that your arcs are not allowed to have the same tail. Therefore, I would divide many arcs into several “bins” that are defined by the tail of the arc. That is, you take each arc, look at its tail and put it in the appropriate box.

Consider a graph consisting of the following arcs:

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

Then we have something like the following:

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

, . , .

: , . .