Description
Book SynopsisContains the proceedings of the first DIMACS workshop. This work covers topics including multicommodity flows, graph matchings and colorings, the traveling salesman problem, integer programming and complexity theory. It is suitable for researchers in combinatorics and combinatorial optimization.
Table of ContentsMatrix cones, projection representations, and stable set polyhedra by L. Lovasz and A. Schrijver A generalization of Lovasz's $\theta$ function by G. Narasimhan and R. Manber On cutting planes and matrices by A. M. H. Gerards Random volumes in the $n$-cube by M. E. Dyer, A. Furedi, and C. McDiarmid Test sets for integer programs, $\forall \exists$ sentences by R. Kannan Solvable classes of generalized traveling salesman problems by S. N. Kabadi and R. Chandrasekaran Handles and teeth in the symmetric traveling salesman polytope by D. Naddef On the complexity of branch and cut methods for the traveling salesman problem by W. Cook and M. Hartmann Existentially polytime theorems by K. Cameron and J. Edmonds The width-length inequality and degenerate projective planes by A. Lehman On Lehman's width-length characterization by P. D. Seymour Applications of polyhedral combinatorics to multicommodity flows and compact surfaces by A. Schrijver Vertex-disjoint simple paths of given homotopy in a planar graph by A. Frank and A. Schrijver On disjoint homotopic paths in the plane by A. Frank On the complexity of the disjoint paths problem (extended abstract) by M. Middendorf and F. Pfeiffer The paths-selection problem by M. Middendorf and F. Pfeiffer Planar multicommodity flows, max cut, and the Chinese postman problem by F. Barahona The cographic multiflow problem: An epilogue by A. Sebo Exact edge-colorings of graphs without prescribed minors by O. Marcotte On the chromatic index of multigraphs and a conjecture of Seymour, (II) by O. Marcotte Spanning trees of different weights by A. Schrijver and P. D. Seymour.
