Network Models: Volume 7

Part 1 Applications of network optimization, R.K. Ahuja et al: preliminaries; shortest paths; maximum flows; minimum cost flows; the assignment problem; matchings; minimum spanning trees; convex cost flows; generalized flows; multicommodity flows; the travelling salesman problem; network design. Part 2 Primal simplex algorithms for minimum cost network flows, R.V. Helgason and J.L. Kennington: primal simplex algorithm; linear network models; generalized networks; multicommodity networks; networks with side constraints. Part 3 Matching, A.M.H. Gerards: finding a matching of maximum cardinality; bipartite matching duality; non-bipartite matching duality; matching and integer and linear programming; finding maximum and minimum weight matchings; general degree constraints; other matching algorithms; applications of matchings; computer implementations and heuristics. Part 4 The travelling salesman problem, M. Junger et al: related problems; practical applications; approximation algorithms for the TSP; relaxations; finding optimal and provably good solutions; computation. Part 5 Parallel computing in network optimization, D. Bertsekas et al: linear network optimization; nonlinear network optimization. Part 6 Probabilistic networks and network algorithms, T.L. Snyder and J.M. Steele: probability theory of network characteristics; probabilistic network algorithms; geometric networks. Part 7 A survey of computational geometry, J.S.B. Mitchell and S. Suri: fundamental structures; geometric graphs; path planning; matching, travelling salesman; and watchman routes; shape analysis, computer vision, and pattern matching. Part 8 Algorithmic implications of the graph minor theorem, D. Bienstock and M.A. Langston: a brief outline of the graph minors project; treewidth; pathwidth and cutwidth; disjoint paths; challenges to practicality. Part 9 Optimal trees, T.L. Magnanti and L.A. Wolsey: tree optimization problems; minimum spanning trees; rooted subtrees of a tree; polynomially solvable extensions/variations; the steiner tree problem; packing subtrees of a tree; packing subtrees of a general graph; trees-on-trees. Part 10 Design of survivable networks, M. Grotschel et al: overview; motivation; integer programming models of survivability; structural properties and heuristics; polynomially solvable special cases; polyhedral results; computational results; directed variants of the general model. Part 11 Network reliability, M.O. Ball et al: motivation; computational complexity and relationships among problems; exact computation of reliability; bounds on network reliability; Monte Carlo methods; performability analysis and multistate network systems; using computational techniques in practice.