Networks and algorithms: an introductory approach.

*(English)*Zbl 0839.90130
Chichester: Wiley. 544 p. $ 99.00/hbk; $ 42.95/pbk (1993).

Publisher’s description: The authors provide a comprehensive introduction to this topic and its many applications. Detailed solution procedures (usually in the form of an algorithm) are given to a wide range of central network 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. The presentation, clarity and arrangement of the material make it ideal for independent study as well as for use with conventional teaching. Algorithms are worked through, step-by-step, and problems (with fully worked solutions) are regularly provided to enable students to test and reinforce their learning.

Contents: Graphs and digraphs. Flows in basic networks. Variations on the basic flow problem. Multi-terminal flows. Paths and connectivity. Longest and shortest path algorithms. Trees. Physical networks: Modeling. Electrical networks: Matrix equations. Electrical networks: solving the equations. Matching problems. The assignment problem. The transportation problem. Critical path analysis. Scheduling. Packing problems. Location problems. Theory of network analysis. Algorithms and NP-completeness. Suggestions for further reading. Solutions to problems in the text. Index.

Contents: Graphs and digraphs. Flows in basic networks. Variations on the basic flow problem. Multi-terminal flows. Paths and connectivity. Longest and shortest path algorithms. Trees. Physical networks: Modeling. Electrical networks: Matrix equations. Electrical networks: solving the equations. Matching problems. The assignment problem. The transportation problem. Critical path analysis. Scheduling. Packing problems. Location problems. Theory of network analysis. Algorithms and NP-completeness. Suggestions for further reading. Solutions to problems in the text. Index.

##### MSC:

90C35 | Programming involving graphs or networks |

90B80 | Discrete location and assignment |

90-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming |

90C10 | Integer programming |

90C27 | Combinatorial optimization |

90C60 | Abstract computational complexity for mathematical programming problems |

90B10 | Deterministic network models in operations research |