数学物理学报(英文版) ›› 2002, Vol. 22 ›› Issue (2): 207-212.

• 论文 • 上一篇    下一篇

AN INVERSE MAXIMUM CAPACITY PATH PROBLEM WITH LOWER BOUND CONSTRAINTS

 杨超, 陈学旗   

  1. College of Management, Huazhong University of Science and Technology, Wuhan 430074, China
  • 出版日期:2002-04-15 发布日期:2002-04-15
  • 基金资助:

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

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)

摘要:

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.

关键词: Maximum capacity path, computational complexity, inverse problem, polynomial algorithm

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

中图分类号: 

  • 90C