Bonn Workshop on Combinatorial Optimization (eBook)

Cover 1
Bonn Workshop on Combinatorial Optimization 4
Copyright Page 5
TOC$Contents 7
Preface 6
List of Participants 7
CH$Chapter 1. Parity graphs 12
CH$Chapter 2. The travelling salesman polytope and {0,2}-matchings 38
CH$Chapter 3. Polyhedra for composed independence systems 68
CH$Chapter 3. Augmenting paths and a class of independence systems 80
CH$Chapter 4. Transformations which preserve perfectness and h-perfectness of graphs 94
CH$Chapter 5. An algorithm for submodular functions on graphs 108
CH$Chapter 6. Optimal subtrees and extensions 132
CH$Chapter 7. Cycles through prescribed and forbidden point sets 140
CH$Chapter 8. An efficient primal simplex algorithm for maximum weighted vertex packing on bipartite graphs 160
CH$Chapter 9. Degree-two inequalities, clique facets, and biperfect graphs 180
CH$Chapter 10. Flow network formulations of polymatroid optimization problems 200
CH$Chapter 11. Two lines least squares 212
CH$Chapter 12. Bounding the independence number of a graph 224
CH$Chapter 13. Scheduling problems with a singular solution 236
CH$Chapter 14. Ear decompositions of elementary graphs and GF2-rank of perfect matchings 252
CH$Chapter 15. Min–max relations for directed graphs 272
CH$Chapter 16. The bandwidth problem: critical subgraphs and the solution for caterpillars 292
CH$Chapter 17. Minimization of some nonlinear functions over polymatroidal network flows 298