Network Programming

Internet Edition

Katta G. Murty
Dept. of Industrial and Operations Engineering
The University of Michigan, Ann Arbor
URL: http://www-personal.umich.edu/~murty/
© 2006 by Katta G. Murty. All rights reserved.

OVERVIEW

This book is first published by Prentice hall in 1992.For my 70th birthday coming this year, I have decided to make it widely accessible by posting it in the form of PDF files of the various chapters separately at this public website. Changes and recompilation have increased the number of pages in this internet edition to 824. So page numbers in the internet edition do not correspond to those in the paper copy of the book.

The book provides an in-depth and clear treatment of common network flow and 1-matching/edge covering problems, theory related to them, and algorithms for them.

Any contributions from the users, or funding to continue this work for providing quality books on OR, Decision making, on public websites will be greatly appreciated.

CONTENTS

 Preface 
 Glossary 
1.Network Definitions, Formulations 
2.Single Commodity Maximum Value Flow Problems in Pure Networks 
3.Primal-Dual and Dual Algorithms for Assignment, Transportation Problems 
4.Shortest Chain Algorithms 
5.Algorithms for Minimum Cost Flows in Pure Networks 
6.Single Commodity Flows with Additional Linear Constraints 
7.Critical Path Methods 
8.Generalized Network Flows 
9.The Minimum Cost Spanning Tree Problem 
10.Blossom Algorithms for 1-Matching/Edge Covering Problems in Undirected Networks