Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a directed graph $G\langle V,E\rangle$, and weight $w[u][v]$ of each $\langle u,v \rangle$ representing an edge of $E$ the question is, try to divide the whole graph into several "rings", making each vertex $u$ belong to a certain "ring" and a "ring" contains at least two vertices, it's guaranteed that the given graph must be able to be divided, satisfying the restrictions.

Finally, please make the total weight of all the "ring"s minimum .

This is a task assigned by my tutor, I don't know if it's an old problem because I'm new on algorithm, my tutor told me that it could be solved within polynomial time complexity, I wanna know how it can be done, I just have no idea about that...

PS: I'm terribly sorry for my forgetting to post the correct question at the first time...

share|cite|improve this question
Your title says 'minimum', but your statement of the problem doesn't. (Nor does it use the weights w[u][v].) Please clarify! – TonyK Dec 23 '10 at 19:18
What exactly do you mean by ring? – Mariano Suárez-Alvarez Dec 24 '10 at 14:39
I assume 'rings' means 'disjoint cycles'. – TonyK Dec 24 '10 at 15:12
up vote 1 down vote accepted

Use any algorithm for Maximum Weighted Bipartite Matching.

share|cite|improve this answer
Got it~ Thanks Yuval Filmus~ – genxium Dec 25 '10 at 4:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.