Acta mathematica scientia,Series B ›› 2002, Vol. 22 ›› Issue (2): 207-212.

• Articles • Previous Articles     Next Articles

AN INVERSE MAXIMUM CAPACITY PATH PROBLEM WITH LOWER BOUND CONSTRAINTS

 YANG Chao, CHEN Xue-Qi   

  1. College of Management, Huazhong University of Science and Technology, Wuhan 430074, China
  • Online:2002-04-15 Published:2002-04-15
  • Supported by:

    The authors gratefully acknowledge the partial support of national natural Founda-tion (Grant 70071011)

Abstract:

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.

Key words: Maximum capacity path, computational complexity, inverse problem, polynomial algorithm

CLC Number: 

  • 90C
Trendmd