I am struggling with the understanding of the (quite famous) paper on lexicographical flows:

Maximal, Lexicographic, and Dynamic Network Flows - by Edward Minieka

The definition of the problem seems really similar to a multi-commodity flow problem. Specifically, instead of the demands constraint, there seems to be a more general (and permissive) one.

I can't really get how the multi-commodity flow problem is NP-complete, while formulation by Minieka is polynomially solvable.

I feel like I am missing something on the purpose of this paper. What does it mean with "departure pattern". Can't I, indeed, always find such a "pattern" within multi-commodity formulation? Doesn't this make any multi-commodity flow problem polynomially solvable?

I am sorry if my question is a bit confusing, but the world of network problems is huge and it's really hard for me to keep it rigor.



Your Answer

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

Browse other questions tagged or ask your own question.