Includes bibliographical references (pages 187-188) and index.

Print version record.

Dr Smith here presents essential mathematical and computational ideas of network optimisation for senior undergraduate and postgraduate students in mathematics, computer science and operational research. He shows how algorithms can be used for finding optimal paths and flows, identifying trees in networks, and optimal matching. Later chapters discuss postman and salesperson tours, and demonstrate how many network problems are related to the ''minimal-cost feasible-flow'' problem. Techniques are presented both informally and with mathematical rigour and aspects of computation, especially of complexity, have been included. Numerous examples and diagrams illustrate the techniques and applications. The book also includes problem exercises with tutorial hints. Presents essential mathematical and computational ideas of network optimisation for senior undergraduate and postgraduate students in mathematics, computer science and operational researchDemonstrates how algorithms can be used for finding optimal paths and flows, identifying trees in networks and optimal matchingNumerous examples and diagrams illustrate the techniques and applications.

Front Cover; ABOUT OUR AUTHOR; Networks and Graphs: Techniques and Computational Methods; Copyright Page; Table of Contents; Preface; Chapter 1. Introduction; 1.1 Graphs and networks; 1.2 Algorithms; 1.3 Basic definitions; 1.4 Complexity of algorithms; 1.5 Optimisation; 1.6 Heuristics; 1.7 Integer programmes; 1.8 Exercises; Chapter 2. Trees; 2.1 Introduction; 2.2 Minimal spanning trees; 2.3 Rooted trees; 2.4 Exercises; Chapter 3. Shortest Paths; 3.1 Introduction; 3.2 Path and other network problems; 3.3 Applications; 3.4 The shortest path algorithm; 3.5 Obvious and important extensions.

3.6 ExercisesChapter 4. Maximum Flows; 4.1 Introduction; 4.2 Ford-Fulkerson method; 4.3 Multiple sources and destinations; 4.4 Constrained flow through a vertex; 4.5 Exercises; Chapter 5. How to Store a Network; 5.1 Introduction; 5.2 Vertex-edge incidence matrix; 5.3 Vertex-vertex adjacency matrix; 5.4 Adjacency lists; 5.5 Forward and reverse star representations; 5.6 Summary; 5.7 Undirected edges; 5.8 Exercises; Chapter 6. More about Shortest Paths; 6.1 Introduction; 6.2 Ford's algorithm; 6.3 The two-tree variant of Dijkstra; 6.4 All shortest-paths; 6.5 The cascade methods.

6.6 Applications of all shortest paths6.7 Exercises; Chapter 7. Advanced Maximal Flow; 7.1 Introduction; 7.2 The E-K modification; 7.3 Prefiow-Push algorithms; 7.4 Summary and notes; 7.5 Exercises; Chapter 8. Minimum-Cost Feasible-Flow; 8.1 Introduction; 8.2 Modelling problems; 8.3 Maximal flow; 8.4 Dealing with personal data; 8.5 The transportation problem; 8.6 Assignment; 8.7 Knapsack problems; 8.8 Transshipment; 8.9 Exercises; Chapter 9. Matching and Assignment; 9.1 Introduction; 9.2 Applications; 9.3 Maximum cardinality; 9.4 General graphs and Edmonds' algorithm.

9.5 Matchings of optimal weight9.6 Exercises; Chapter 10. Postman Problems; 10.1 Introduction; 10.2 Applications and notes; 10.3 Postman problem: undirected networks; 10.4 Postman tours in mixed networks; 10.5 Problems related to the postman problem; 10.6 Exercises; Chapter 11. Travelling Salesperson; 11.1 Introduction; 11.2 Background and applications; 11.3 Heuristics for the travelling salesperson problem; 11.4 Finding an optimal solution to the TSP; 11.5 Exercises; Chapter 12. Tutorial hints; Books and References; Index.

Elsevier ScienceDirect All Books