## Network flows: theory, algorithms, and applicationsBringing together the classic and the contemporary aspects of the field, this comprehensive introduction to network flows provides an integrative view of theory, algorithms, and applications. It offers in-depth and self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including a description of new and novel polynomial-time algorithms for these core models. For professionals working with network flows, optimization, and network programming. |

### What people are saying - Write a review

User Review - Flag as inappropriate

Approachable, powerful text.

### Contents

INTRODUCTION | 1 |

PATHS TREES AND CYCLES | 23 |

ALGORITHM DESIGN AND ANALYSIS | 53 |

Copyright | |

25 other sections not shown

### Common terms and phrases

adjacency list algorithm performs Application arc costs arc flows arc i,j arc lengths augmenting path algorithm bipartite capacity scaling algorithm commodity constraints cost flow problem define denote Dijkstra's algorithm directed cycle directed network directed path discussion distance label example Exercise feasible flow feasible solution Fibonacci heap flow algorithms formulation implementation integer iteration label-correcting algorithm Lagrangian multiplier Lagrangian relaxation Lemma linear programming lower bound matching matrix maximum flow problem minimum cost flow minimum spanning tree multicommodity flow problem negative cycle network contains network flow problem network G network simplex algorithm node potentials nonnegative objective function value operation optimal solution optimality conditions path from node polynomial preflow-push algorithm reduced cost residual network s-t cut satisfies scaling phase Section shortest path distances shortest path problem Show shown in Figure simplex method sink node source node Suppose Theorem undirected units of flow upper bound variables zero