Chandru, Vijaya ; Coullard, Collette R ; Wagner, Donald K (1985) On the complexity of recognizing a class of generalized networks Operations Research Letters, 4 (2). pp. 75-78. ISSN 01676377
Full text not available from this repository.
Official URL: http://doi.org/10.1016/0167-6377(85)90036-7
Related URL: http://dx.doi.org/10.1016/0167-6377(85)90036-7
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V |
| Keywords: | network flows;problem equivalence;computational complexity;matroids |
| ID Code: | 132619 |
| Deposited On: | 20 Dec 2022 08:44 |
| Last Modified: | 20 Dec 2022 08:44 |
Repository Staff Only: item control page
