## Adjacency on polytopes in combinatorial optimization |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction and summary of results | 3 |

Fundamentals | 10 |

Coloring criteria | 53 |

Copyright | |

4 other sections not shown

### Common terms and phrases

0-1 polytopes 1-coloring acyclic relations adjacency characterization adjacent with respect arborescence assignment polytope b-matchings circuit coarsest simply feasible color classes coloring with respect combinatorial optimization comparability graph complete digraph complete set connected component contact vertex contains contradiction convex combination corresponding criteria criterion with respect definition different from F distinct S-sets edges uv elementary cycle exists F are adjacent F U F F1 U F2 graph G Hence hypergraph implicant graph implicants of E,S incidence matrix independence system K U L Lemma Let E,S let F linear orderings matrix matroid necessary and sufficient nonvoid obtain Padberg partial coloring partial orderings path polytope P(S prime implicant Proof proper partition respect to E,S satisfying set of implicants set partitioning polytope simple coloring algorithm simple coloring criterion simplex algorithm simply feasible coloring subset F C E subsets E,S system of subsets Theorem Un-criterion vertices