著者紹介

内容

目次

Part 1 Applications of network optimization, R.K. Ahuja et al:preliminaries; shortest paths; maximum flows; minimum cost flows; theassignment 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 networkflows, R.V. Helgason and J.L. Kennington: primal simplex algorithm; linearnetwork models; generalized networks; multicommodity networks; networks withside constraints. Part 3 Matching, A.M.H. Gerards: finding a matching ofmaximum cardinality; bipartite matching duality; non-bipartite matchingduality; matching and integer and linear programming; finding maximum andminimum weight matchings; general degree constraints; other matchingalgorithms; applications of matchings; computer implementations andheuristics. Part 4 The travelling salesman problem, M. Junger et al: relatedproblems; practical applications; approximation algorithms for the TSP;relaxations; finding optimal and provably good solutions; computation. Part 5Parallel computing in network optimization, D. Bertsekas et al: linearnetwork optimization; nonlinear network optimization. Part 6 Probabilisticnetworks and network algorithms, T.L. Snyder and J.M. Steele: probabilitytheory 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; pathplanning; matching, travelling salesman; and watchman routes; shape analysis,computer vision, and pattern matching. Part 8 Algorithmic implications of thegraph minor theorem, D. Bienstock and M.A. Langston: a brief outline of thegraph 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 subtreesof a tree; polynomially solvable extensions/variations; the steiner treeproblem; 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; structuralproperties and heuristics; polynomially solvable special cases; polyhedralresults; computational results; directed variants of the general model. Part11 Network reliability, M.O. Ball et al: motivation; computational complexityand relationships among problems; exact computation of reliability; bounds onnetwork reliability; Monte Carlo methods; performability analysis andmultistate network systems; using computational techniques in practice.