Applying Lehman's theorems to packing problems
From MaRDI portal
Publication:1919808
DOI10.1007/BF01590960zbMath0863.05052MaRDI QIDQ1919808
Publication date: 18 September 1996
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
ideal matrixperfect matricesstable set polytopesblocking matrixpacking polyhedratotal dual integrability
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs ⋮ Lehman's Theorem and the Directed Steiner Tree Problem ⋮ Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs ⋮ Complementation in T-perfect graphs ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ On claw-free \(t\)-perfect graphs ⋮ Characterizing N+-perfect line graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope ⋮ On circular-perfect graphs: a survey ⋮ On circulant thin Lehman matrices ⋮ Clique-circulants and the stable set polytope of fuzzy circular interval graphs ⋮ The stable set polytope of quasi-line graphs ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ On classes of minimal circular-imperfect graphs ⋮ A note on kernels and Sperner's Lemma ⋮ Unnamed Item ⋮ On the commutativity of antiblocker diagrams under lift-and-project operators ⋮ On a certain class of nonideal clutters ⋮ On packing and covering polyhedra of consecutive ones circulant clutters ⋮ Computing the clique number of \(a\)-perfect graphs in polynomial time ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ Characterizing and bounding the imperfection ratio for some classes of graphs ⋮ Triangle-free strongly circular-perfect graphs ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ Unnamed Item ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ Some advances on Lovász-Schrijver relaxations of the fractional stable set polytope ⋮ Near-perfect graphs with polyhedral ⋮ Non-regular square bipartite designs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lehman's forbidden minor characterization of ideal 0-1 matrices
- Matrices with the Edmonds-Johnson property
- A generalization of antiwebs to independence systems and their canonical facets
- Graphical properties related to minimal imperfection
- On stable set polyhedra for K//(1,3)free graphs
- Almost integral polyhedra related to certain combinatorial optimization problems
- Ideal 0, 1 matrices
- Near-perfect matrices
- On certain polytopes associated with graphs
- Normal hypergraphs and the perfect graph conjecture
- On the width—length inequality
- Perfect triangle-free 2-matchings
- Finite checkability for integer rounding properties in combinatorial programming problems
- The Forbidden Minors of Binary Clutters
- Perfect zero–one matrices
- Bottleneck extrema
