Flows in Networks.

Format:

Book

Author/Creator:

Ford, Lester Randolph.

Contributor:

Fulkerson, D. R.

Bland, Robert G.

Orlin, James B.

Series:

Princeton Landmarks in Mathematics and Physics Series

Language:

English

Subjects (All):

Graph theory.

Linear programming.

Physical Description:

1 online resource (217 pages)

Edition:

1st ed.

Place of Publication:

Princeton : Princeton University Press, 2010.

Summary:

A landmark work that belongs on the bookshelf of every researcher working with networksIn this classic book, first published in 1962, L. R. Ford, Jr., and D. R. Fulkerson set the foundation for the study of network flow problems. The models and algorithms introduced in Flows in Networks are used widely today in the fields of transportation systems, manufacturing, inventory planning, image processing, and Internet traffic. The techniques presented by Ford and Fulkerson spurred the development of powerful computational tools for solving and analyzing network flow models, and also furthered the understanding of linear programming. In addition, the book helped illuminate and unify results in combinatorial mathematics while emphasizing proofs based on computationally efficient construction. With an incisive foreword by Robert Bland and James Orlin, Flows in Networks is rich with insights that remain relevant to current research in engineering, management, and other sciences.

Contents:

Frontmatter

CONTENTS

Foreword to the 2010 edition

PREFACE

ACKNOWLEDGMENTS

CHAPTER I STATIC MAXIMAL FLOW

Introduction

1. Networks

2. Flows in networks

3. Notation

4. Cuts

5. Maximal flow

6. Disconnecting sets and cuts

7. Multiple sources and sinks

8. The labeling method for solving maximal flow problems

9. Lower bounds on arc flows

10. Flows in undirected and mixed networks

11. Node capacities and other extensions

12. Linear programming and duality principles

13. Maximal flow value as a function of two arc capacities

References

CHAPTER II FEASIBILITY THEOREMS AND COMBINATORIAL APPLICATIONS

1. A supply-demand theorem

2. A symmetric supply-demand theorem

3. Circulation theorem

4. The König-Egerváry and Menger graph theorems

5. Construction of a maximal independent set of admissible cells

6. A bottleneck assignment problem

7. Unicursal graphs

8. Dilworth's chain decomposition theorem for partially ordered sets

9. Minimal number of individuals to meet a fixed schedule of tasks

10. Set representatives

11. The subgraph problem for directed graphs

12. Matrices composed of O's and l's

CHAPTER III MINIMAL COST FLOW PROBLEMS

1. The Hitchcock problem

2. The optimal assignment problem [56, 57, 60, 61, 68, 69]

3. The general minimal cost flow problem

4. Equivalence of Hitchcock and minimal cost flow problems

5. A shortest chain algorithm

6. The minimal cost supply-demand problem: non-negative directed cycle costs

7. The warehousing problem

8. The caterer problem

9. Maximal dynamic flow

10. Project cost curves

11. Constructing minimal cost circulations [28]

CHAPTER IV MULTI-TERMINAL MAXIMAL FLOWS

1. Forests, trees, and spanning subtrees

2. Realization conditions

3. Equivalent networks

4. Network synthesis

INDEX

Notes:

Description based on publisher supplied metadata and other sources.

ISBN:

9780691273457

0691273456

OCLC:

927972280