Minimum Cost Maximum Flow Problem

No Thumbnail Available

Date

2017-06

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

Citation

Collections