Minimum Cost Maximum Flow Problem
No Thumbnail Available
Date
2017-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
This work presents an algorithm for computing the maximum flow and minimum cost flow problem of undirected graphs, based on the well-known algorithm presented by Ford and Fulkerson for directed graphs. The new algorithm is equivalent to just applying Ford and Fulkerson algorithm to the directed graph obtained from original graph but with two directed arcs for each edge in the graph, one in each way.
We shall also discuss a range of network problems and finally discuss in details the minimum cost maximum flow problem. Network models in this chapter will focus on techniques of finding the most efficient ways of finding the shortest route between two locations; determine the minimum-cost flow in a network that satisfies supply and demand requirements that will produce maximum flow in the network.
Goal: Build a cheap network to satisfy the flow requirement
Keywords: Max Flow, Minimum Cost, Parametric Flow
Description
Keywords
Max Flow, Minimum Cost, Parametric Flow