The Minimum‐Cost Dynamic Flow Problem in a Fixed Graph With a Constant Target Flow Value Article Swipe
A dynamic network is a directed graph where an arc has a capacity and a transit time. A dynamic flow is a flow defined in a dynamic network. We consider the problem of finding a minimum‐cost dynamic flow in a dynamic network where an arc has a cost. It is known that this problem is NP‐hard. Klinz and Woeginger asked whether the minimum‐cost dynamic flow problem in a fixed graph (i.e., a graph is given a priori, and it is not a part of the input) can be solved in polynomial time. We prove that if the cost of each arc is non‐negative, the capacity of each arc is an integer, and the target flow value is a constant integer, then this problem can be solved in polynomial time.
Related Topics To Compare & Contrast
Concepts
Constant (computer programming)
Minimum-cost flow problem
Flow (mathematics)
Multi-commodity flow problem
Graph
Mathematical optimization
Computer science
Mathematics
Value (mathematics)
Flow network
Combinatorics
Geometry
Statistics
Programming language
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1002/net.22272
- https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272
- OA Status
- bronze
- Cited By
- 1
- References
- 17
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4407938902
All OpenAlex metadata
Raw OpenAlex JSON
No additional metadata available.