A class of facet producing graphs for vertex packing polyhedra
From MaRDI portal
Publication:1220520
DOI10.1016/0012-365X(75)90077-1zbMath0314.05111OpenAlexW2059909742MaRDI QIDQ1220520
Publication date: 1975
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(75)90077-1
Related Items
On the Chvátal-rank of Antiwebs, Persistency of Linear Programming Relaxations for the Stable Set Problem, Vertex packing problem application to the design of electronic testing fixtures, Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs, Some advances on the set covering polyhedron of circulant matrices, A construction for non-rank facets of stable set polytopes of webs, Tree-width and the Sherali-Adams operator, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs, New facets for the two-stage uncapacitated facility location polytope, On ternary problems, On the 0,1 facets of the set covering polytope, A generalization of antiwebs to independence systems and their canonical facets, The Boolean quadratic polytope: Some characteristics, facets and relatives, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, On cutting-plane proofs in combinatorial optimization, Facets and lifting procedures for the set covering polytope, Generating irreducible copositive matrices using the stable set problem, Strong lift-and-project cutting planes for the stable set problem, Facet-inducing web and antiweb inequalities for the graph coloring polytope, Graphical properties related to minimal imperfection, Total coloring and total matching: polyhedra and facets, On the facets of stable set polytopes of circular interval graphs, On the complete set packing and set partitioning polytopes: properties and rank 1 facets, $t$-Perfection in $P_5$-Free Graphs, Colorings of complements of line graphs, An extended formulation for the 1‐wheel inequalities of the stable set polytope, New variants of the simple plant location problem and applications, On the 2-Club Polytope of Graphs, Polytope des independants d'un graphe série-parallèle, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, On the facets of the stable set polytope of quasi-line graphs, Clique family inequalities for the stable set polytope of quasi-line graphs., 2-clique-bond of stable set polyhedra, On stable set polyhedra for K//(1,3)free graphs, On the Chvátal rank of linear relaxations of the stable set polytope, Clique-circulants and the stable set polytope of fuzzy circular interval graphs, Transitive packing, New valid inequalities and facets for the simple plant location problem, Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope, On the mixed set covering, packing and partitioning polytope, New facets for the set packing polytope, On classes of minimal circular-imperfect graphs, RLT insights into lift-and-project closures, A class of web-based facets for the generalized vertex packing problem, Unnamed Item, Exploring the relationship between max-cut and stable set relaxations, On non-rank facets of stable set polytopes of webs with clique number four, A polyhedral study of the generalized vertex packing problem, Searching for mutually orthogonal Latin squares via integer and constraint programming, An exact approach to the problem of extracting an embedded network matrix, Polyhedral properties of the induced cluster subgraphs, On packing and covering polyhedra of consecutive ones circulant clutters, Lifting the facets of zero–one polytopes, A polyhedral study on 0-1 knapsack problems with set packing constraints, Extended formulations for vertex cover, Computing the clique number of \(a\)-perfect graphs in polynomial time, Gear composition and the stable set polytope, Valid inequalities and facets of the capacitated plant location problem, On the set covering polyhedron of circulant matrices, Strengthened clique-family inequalities for the stable set polytope, Triangle-free strongly circular-perfect graphs, Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, Facets and algorithms for capacitated lot sizing, Unnamed Item, Unnamed Item, Unnamed Item, A lower bound on the Chvátal-rank of Antiwebs, A new lifting theorem for vertex packing, A note on node packing polytopes on hypergraphs, Dynamic node packing, Almost all webs are not rank-perfect, Some facets of the simple plant location polytope, On determining the imperfection ratio, The maximum clique problem, \(K_ i\)-covers. I: Complexity and polytopes, Persistency of linear programming relaxations for the stable set problem, A conditional logic approach for strengthening mixed 0-1 linear programs, Light on the infinite group relaxation. I: Foundations and taxonomy
Cites Work
- Anti-blocking polyhedra
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- Technical Note—A Note on Zero-One Programming
- Vertex packings: Structural properties and algorithms
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Line perfect graphs
- Report of the Session on Algorithms for Special Classes of Combinatorial Optimization Problems
- Properties of vertex packing and independence system polyhedra
- Perfect zero–one matrices
- On the facial structure of set packing polyhedra
- Point-symmetric graphs with a prime number of points
- The Strong Perfect Graph Conjecture for Planar Graphs
- The complexity of theorem-proving procedures
- Blocking and anti-blocking pairs of polyhedra
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
