2

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?

Improve this question

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Note that in this case, each "bin" is actually just a node in the graph, so all you are doing is going through the list nodes and picking the exiting arc that has the greatest weight. Also, I would not recommended walking the graph because it does not seem you are guaranteed that the graph is connected.
@B_ I do not suggest to walk the graph along it's connections, but I suggest traversing the list of arcs.
My mistake, misunderstood your suggestion.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.