-
Book DetailsDIMACS - Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 1; 1990; 288 ppMSC: Primary 05; 90
This book, the first volume in the DIMACS book series, contains the proceedings of the first DIMACS workshop. The workshop, which was held in June 1989 in Morristown, New Jersey, focused on polyhedral combinatorics. Two series of lectures were presented by L. Lovász and A. Schrijver and there were a number of shorter lectures. The topics covered include multicommodity flows, graph matchings and colorings, the traveling salesman problem, integer programming, and complexity theory. Aimed at researchers in combinatorics and combinatorial optimization, this book will provide readers with an overview of recent advances in combinatorial optimization.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).
-
Table of Contents
-
Chapters
-
Matrix cones, projection representations, and stable set polyhedra
-
A generalization of Lovász’s $\theta $ function
-
On cutting planes and matrices
-
Random volumes in the $n$-cube
-
Test sets for integer programs, $\forall \exists $ sentences
-
Solvable classes of generalized traveling salesman problems
-
Handles and teeth in the symmetric traveling salesman polytope
-
On the complexity of branch and cut methods for the traveling salesman problem
-
Existentially polytime theorems
-
The width-length inequality and degenerate projective planes
-
On Lehman’s width-length characterization
-
Applications of polyhedral combinatorics to multicommodity flows and compact surfaces
-
Vertex-disjoint simple paths of given homotopy in a planar graph
-
On disjoint homotopic paths in the plane
-
On the complexity of the disjoint paths problem (extended abstract)
-
The paths-selection problem
-
Planar multicommodity flows, max cut, and the Chinese postman problem
-
The cographic multiflow problem: An epilogue
-
Exact edge-colorings of graphs without prescribed minors
-
On the chromatic index of multigraphs and a conjecture of Seymour, (II)
-
Spanning trees of different weights
-
- Book Details
- Table of Contents
This book, the first volume in the DIMACS book series, contains the proceedings of the first DIMACS workshop. The workshop, which was held in June 1989 in Morristown, New Jersey, focused on polyhedral combinatorics. Two series of lectures were presented by L. Lovász and A. Schrijver and there were a number of shorter lectures. The topics covered include multicommodity flows, graph matchings and colorings, the traveling salesman problem, integer programming, and complexity theory. Aimed at researchers in combinatorics and combinatorial optimization, this book will provide readers with an overview of recent advances in combinatorial optimization.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).
-
Chapters
-
Matrix cones, projection representations, and stable set polyhedra
-
A generalization of Lovász’s $\theta $ function
-
On cutting planes and matrices
-
Random volumes in the $n$-cube
-
Test sets for integer programs, $\forall \exists $ sentences
-
Solvable classes of generalized traveling salesman problems
-
Handles and teeth in the symmetric traveling salesman polytope
-
On the complexity of branch and cut methods for the traveling salesman problem
-
Existentially polytime theorems
-
The width-length inequality and degenerate projective planes
-
On Lehman’s width-length characterization
-
Applications of polyhedral combinatorics to multicommodity flows and compact surfaces
-
Vertex-disjoint simple paths of given homotopy in a planar graph
-
On disjoint homotopic paths in the plane
-
On the complexity of the disjoint paths problem (extended abstract)
-
The paths-selection problem
-
Planar multicommodity flows, max cut, and the Chinese postman problem
-
The cographic multiflow problem: An epilogue
-
Exact edge-colorings of graphs without prescribed minors
-
On the chromatic index of multigraphs and a conjecture of Seymour, (II)
-
Spanning trees of different weights
