Given a graph with positive edge weight representing "time to travel through", and 2 or more pairs of start/end vertices, we can find concurrent paths for the pairs such that the maximum cumulative weight along any path is minimum, using classic shortest path algorithms.

Now what if the weight is not static, but represents "congestion penalty", i.e. the weight will be larger if the edge appears in 2 paths in the solution (and increase even more as being shared by more paths)?

Are there algorithms for such a case (or something similar)? Is this NP-hard? We can assume only 2 pairs, all 4 vertices distinct, weights are positive integers, and such.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.