AN INVERSE MAXIMUM CAPACITY PATH PROBLEM WITH LOWER BOUND CONSTRAINTS

摘要

The computational complexity of inverse mimimum capacity path problem with lower bound on capacity of maximum capacity path is examined, and it is proved that solution of this problem is NP-complete. A strong polynomial algorithm for a local optimal solution is provided.