On the complexity of circulations |
| |
Affiliation: | Department of Operations Research, Stanford University, Stanford, CaliforniaUSA;Department of Geography, Ghent University, Ghent 9000, Belgium |
| |
Abstract: | We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|