I have a problem in which I need to solve the realization for a directed graph when I am given the in and out degrees for n number of vertices. A hint was to use network flows. I know that the Kleitman Wang algorithm will help me solve this problem.

However, I am having difficult understanding the Kleitman Wang algorithm. The Wikipedia entry is rather short and doesn't explain what is happening.

I do understand that first, the pairs need to be sorted to be in non-increaising order. However, I do not understand what the definition of $S'$ means, particularly when it says a pair becomes $(a_{b_i-1}-1$,$b_{b_i-1})$

I also do not understand what this algorithm is doing from a theoretical standpoint, especially not in terms of network flows.

If someone could provide insight into understanding the definition of $S'$, and explain how this works in plain english, it would be much appreciated

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.