DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME ONE
TITLE: "POLYHEDRAL COMBINATORICS"
EDITORS: William Cook and Paul D. Seymour
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

PREFACE

This collection of papers constitutes the proceedings of a workshop on polyhedral combinatorics, held from 12th to 16th June 1989, in the Headquarters Plaza Hotel, Morristown, New Jersey. Two series of lectures were given by L. Lovasz and A. Schrijver (a total of three one-hour lectures each), and there were a number of shorter lectures. The meeting was the first in a series of workshops supported by DIMACS (the center for Discrete Mathematics and Theoretical Computer Science). DIMACS is an NSF Science and Technology Center, and it is a collaboration of Bellcore, AT&T Bell Labs, Rutgers University, and Princeton University. We would like to express our thanks to DIMACS and the NSF for their generous support.

All of the papers have been refereed. We have tried to organize the volume as far as possible so that related papers are near to one another.

We regret the death of Martin Farber (AT&T Bell Labs) shortly before the workshop. Martin was a leading figure in polyhedral combinatorics, and this volume includes an orbituary by Pavol Hell.

TABLE OF CONTENTS


Matrix Cones, Projection Representations, and Stable Set Polyhedra
	L. Lovasz and A. Schrijver				     1

A Generalization of Lovasz's 0 Function
	Giri Narasimhan and Rachel Manber			     19

On Cutting Planes and Matrices
	A.M.H. Gerards						     29	

Random Volumes in the n-Cube
	M.E. Dyer, Z. Furedi, and C. McDiarmid                       33

Test Sets for Integer Programs, 0_ Sentences
	Ravi Kannan						     39

Solvable Classes of Generalized Traveling Salesman Polytope
	S.N. Kabadi and R. Chandrasekaran                            49

Handles and Teeth in the Symmetric Traveling Salesman Problems
	Denis Naddef						     61

On the Complexity of Branch and Cut Methods for the Traveling
Salesman Problem
	W. Cook and M. Hartmann                                      75

Existentially Polytime Theorems
	Kathie Cameron and Jack Edmonds                              83

The Width-Length Inequality and Degenerate Projective Planes
	Alfred Lehman                                               101

On Lehman's Width-Length Characterization
	P.D. Seymour                                                107

Applications of Polyhedral Combinatorics to Multicommodity Flows
and Compact Surfaces
	A. Schrijver                                                119
		
Vertex-Disjoint Simple Paths of Given Homotopy in a Planar Graph
	A. Frank and A. Schrijver				    139	     

On Disjoint Homotopic Paths in the Plane
	Andras Frank                                                163        

On the Complexity of the Disjoint Paths Problem (Extended Abstract)
	Matthias Middendorf and Frank, Pfeiffer                     171

The Paths-Selection                                                 179
        Matthias Middendorf and Frank Pfeiffer

Planar Multicommodity Flows, Max Cut, and the Chinese Postman Problem
	Francisco Barahona                                          189

The Cographic Multiflow Problem: An Epilogue
	Andras Sebo                                                 203

Exact Edge-Colorings of Graphs without Prescribed Minors
	Odile Marcotte                                              235

On the Chromatic Index of Multigraphs and a Conjecture of Seymour, (II)
	Odile Marcotte                                              245

Spanning Trees of Different Weights
	A. Schrijver and P.D. Seymour                               281
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.