Networks and Algorithms: An Introductory Approach

Networks and Algorithms An Introductory Approach Alan Dolan, Faculty of Technology, The Open University, Milton Keynes, UK Joan Aldous, Faculty of Mathematics, The Open University, Milton Keynes, UK Network theory has in recent years become a valuable aid to planning and analysis in an increasingly wide range of applications in industry, commerce and government. This book provides a comprehensive introduction to this topic and its applications. Detailed solution procedures (usually in the form of an algorithm) are given to a wide range of central network problems including longest and shortest paths, critical path scheduling, location problems, electrical networks, maximum flow problems and transportation problems. There is also a discussion of the time complexity of algorithms and the theory of NP-completeness. An early chapter provides the basic graph theory required for a study of networks. Particular attention has been paid to the presentation, clarity and arrangement of the material, making it ideal for independent study as well as for use with conventional teaching. Algorithms are worked through step by step and problems (with complete worked solutions) are regularly provided to enable students to test and reinforce their learning. The book can be used in conjunction with, or as a sequel to, Graphs: An Introductory Approach by Wilson and Watkins, and is ideal for undergraduate students of mathematics, computer science and operational research.