Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Problem reduction to max flow | Reply
Can we have the flow restriction on edge such that either it flows 0 flow or max-capacity but no partial flow ?
IE some node takes input flow from the one node only via edge(max) only
can someone give idea how we can convert the graph to max flow min cost problem ?
Re: Problem reduction to max flow (response to post by aarifjindani) | Reply
The knapsack problem can be reduced to your problem, so your problem is NP-hard. And it is clearly in NP, so it is NP-complete. So, no.