|
|||||
|
|
On the complexity of recognizing a class of generalized networks |
|
| Authors: | Vijaya Chandru Collette R Coullard Donald K Wagner |
| Institution: | School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA |
| Abstract: | The problem of determining whether a given linear programming problem can be converted to a generalized network flow problem having no unit-weight cycles is shown to be NP-hard. The same argument also shows that the problem of determining whether a gain matroid is bicircular is NP-hard. |
| Keywords: | network flows problem equivalence computational complexity matroids |
| 本文献已被 ScienceDirect 等数据库收录！ | |