Degree-two Inequalities, Clique Facets, and Biperfect Graphs

DOI10.1016/S0304-0208(08)72450-2zbMATH Open0523.52009OpenAlexW1548435598MaRDI QIDQ3673580FDOQ3673580

Authors Manfred Padberg, Ellis L. Johnson

Publication date 1982

Published in North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-0208(08)72450-2

zbMATH Keywords

inequalitiesconvex hullpolyhedravertex coveringperfect graphsBoolean programmingset packingclique inequality0-1 solutions

Mathematics Subject Classification ID

Integer programming (90C10) Polytopes and polyhedra (52Bxx) Inequalities and extremum problems involving convexity in convex geometry (52A40) Boolean programming (90C09) Graph theory (05C99)

Recommendations

• Bipartite dimensions and bipartite degrees of graphs
• A variant of the bipartite relation theorem and its application to clique graphs
• Problems and invariants connected with bicliques and multicliques of graphs
• Bipartite Graphs and their Degree Sets
• scientific article; zbMATH DE number 19220
• A degree condition of 2-factors in bipartite graphs
• Degree-bounded factorizations of bipartite multigraphs and of pseudographs
• Bicliques in graphs. I: Bounds on their number
• Two-fold factorization of the complete bipartite graphs by infinite graph classes
• Bipartite graphs of large clique-width

Cited in

(20)

• Uniquely solvable quadratic Boolean equations
• A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Structure-driven fix-and-propagate heuristics for mixed integer programming
• Solving a multigroup mixed-integer programming-based constrained discrimination model
• Perfect, ideal and balanced matrices
• Some properties of cliques in 0-1 mixed integer programs
• Worst-case analysis of clique MIPs
• Constraint Integer Programming: A New Approach to Integrate CP and MIP
• Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs
• Conflict graphs in solving integer programming problems
• Presolve Reductions in Mixed Integer Programming
• Binary integer programs with two variables per inequality
• A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
• SCIP: solving constraint integer programs
• Cutting planes in integer and mixed integer programming
• Refined proximity and sensitivity results in linearly constrained convex separable integer programming
• Supernode processing of mixed-integer models
• The maximum clique problem
• Theoretical challenges towards cutting-plane selection

This page was built for publication: Degree-two Inequalities, Clique Facets, and Biperfect Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3673580)