Blocking and anti-blocking pairs of polyhedra

DOI10.1007/BF01584085zbMath0254.90054OpenAlexW2049716158MaRDI QIDQ5668263

Publication date: 1971

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01584085

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Related Items

Snarks with resistance \(n\) and flow resistance \(2n\), Relaxations of vertex packing, The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets, Polyhedral proof methods in combinatorial optimization, On snarks that are far from being 3-edge colorable, Lift-and-project ranks and antiblocker duality, The cost of perfection for matchings in graphs, Reliability, covering and balanced matrices, A reduction procedure for coloring perfect \(K_ 4\)-free graphs, Extremal problems for finite sets and convex hulls---a survey, Interpolating between volume and lattice point enumerator with successive minima, Edge-packings of graphs and network reliability, Total dual dyadicness and dyadic generating sets, A generalization of Robacker's theorem, On the facial structure of the set covering polytope, On the spanning tree polyhedron, Perfect graphs are kernel solvable, Graphical properties related to minimal imperfection, On excessive index of certain networks, Strong formulation for the spot 5 daily photograph scheduling problem, Covering a cubic graph with perfect matchings, On CIS circulants, Graphs of arbitrary excessive class, Sparsely intersecting perfect matchings in cubic graphs, On certain polytopes associated with graphs, The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect, Cores, joins and the Fano-flow conjectures, Entropy of symmetric graphs, Unconditional reflexive polytopes, Discrete extremal problems, On claw-free \(t\)-perfect graphs, Fractional packing in ideal clutters, Unique Fulkerson coloring of Petersen minor-free cubic graphs, Generation and properties of snarks, Graph covers using \(t\)-colourable vertex sets., The complexity of recognizing linear systems with certain integrality properties, A set partitioning reformulation of a school bus scheduling problem, On circular-perfect graphs: a survey, Perfect graphs and norms, Perfect matching covers of cubic graphs of oddness 2, On circulant thin Lehman matrices, Berge-Fulkerson coloring for infinite families of snarks, Measures of edge-uncolorability of cubic graphs, Signed cycle double covers, Integer flows and cycle covers, Cuboids, a class of clutters, Polarity and the complexity of the shooting experiment, Rotation snark, Berge-Fulkerson conjecture and Catlin's 4-flow reduction, On the mixed set covering, packing and partitioning polytope, Lehman's forbidden minor characterization of ideal 0-1 matrices, Separating from the dominant of the spanning tree polytope, The anti-join composition and polyhedra, On cuts and matchings in planar graphs, A partition-based relaxation for Steiner trees, Cutting planes in integer and mixed integer programming, Perfect matchings with restricted intersection in cubic graphs, A class of facet producing graphs for vertex packing polyhedra, A proof of Fulkerson's characterization of permutation matrices, Blocking pairs of polyhedra arising from network flows, Two easy duality theorems for product partial orders, Polyhedral results on the stable set problem in graphs containing even or odd pairs, On a connection between facility location and perfect graphs, On packing and covering polyhedra in infinite dimensions, Almost integral polyhedra related to certain combinatorial optimization problems, Treelike snarks, Families of dot-product snarks on orientable surfaces of low genus, An unbounded matroid intersection polyhedron, A new infinite class of ideal minimally non-packing clutters, Classification de certaines matrices 0-1, Critical perfect graphs and perfect 3-chromatic graphs, Berge-Fulkerson coloring for some families of superposition snarks, The matroids with the max-flow min-cut property, Blocking, antiblocking, and pairs of matroids and polymatroids, Clutters with \(\tau_ 2 \Relbar 2\tau\), Lower bounds on the cover-index of a graph, Group flow, complex flow, unit vector flow, and the \((2 + \epsilon)\)-flow conjecture, On the excessive \([m\)-index of a tree], On ideal semicomplete digraphs, The \(h^\ast\)-polynomials of locally anti-blocking lattice polytopes and their \(\gamma\)-positivity, An abstract duality, Matchings and covers in hypergraphs, A min-max relation for the partial q-colourings of a graph. II: Box perfection, Normal 6-edge-colorings of some bridgeless cubic graphs, Probabilistic refinement of the asymptotic spectrum of graphs, On totally dual integral systems, A note on Berge-Fulkerson coloring, On a geometric property of perfect graphs, Testing membership in matroid polyhedra, Total weak unimodularity: Testing and applications, On the maximum fraction of edges covered by \(t\) perfect matchings in a cubic bridgeless graph, A class of h-perfect graphs, On the integrality of an extreme solution to pluperfect graph and balanced systems, On some weakly bipartite graphs, Testing idealness in the filter oracle model, Path-closed sets, A new proof of a theorem of Harper on the Sperner-Erdős problem, Entropy splitting for antiblocking corners and perfect graphs, Morphology of small snarks, A class of cubic graphs satisfying Berge conjecture, Fano colourings of cubic graphs and the Fulkerson conjecture, Some snarks are worse than others, A Lagrangean decomposition for the maximum independent set problem applied to map labeling, 5-Cycle Double Covers, 4-Flows, and Catlin Reduction, Geometric inequalities for anti-blocking bodies, The equivalence of two conjectures of Berge and Fulkerson, On box totally dual integral polyhedra, Perfect matching covering, the Berge-Fulkerson conjecture, and the Fan-Raspaud conjecture, On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency, Lehman's Theorem and the Directed Steiner Tree Problem, On Perfect Matching Coverings and Even Subgraph Coverings, Clean Clutters and Dyadic Fractional Packings, On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings, Covering a cubic graph by 5 perfect matchings, The anisotropic fractional isoperimetric problem with respect to unconditional unit balls, An Upper Bound for the Excessive Index of an r‐Graph, A Class of Balanced Matrices Arising from Location Problems, Unnamed Item, Polyhedral Combinatorics in Combinatorial Optimization, Two Double Poset Polytopes, Berge–Fulkerson coloring for C(12)‐linked permutation graphs, Ban–Linial's Conjecture and treelike snarks, On Packing Dijoins in Digraphs and Weighted Digraphs, Deltas, extended odd holes and their blockers, On \(d\)-dimensional nowhere-zero \(r\)-flows on a graph, A Sum of Squares Characterization of Perfect Graphs, Dual gauge programs, with applications to quadratic programming and the minimum-norm problem, Total dual integrality implies local strong unimodularity, Deciding whether four perfect matchings can cover the edges of a snark is NP-complete, On the existence of graphs which can colour every regular graph, Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs, Unions of perfect matchings in \(r\)-graphs, Dynamic decomposition method for linear programming problems with ceneralized upper bounds, Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching, Classes of perfect graphs, Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks, A polyhedral study of the semi-continuous knapsack problem, Two-commodity cut-packing problem, Quasi-balanced matrices, Odd 2-factored snarks, A survey of graph coloring - its types, methods and applications, Single-facility scheduling by logic-based Benders decomposition, Precoloring Extension III: Classes of Perfect Graphs, Fulkerson's conjecture and Loupekine snarks, An equivalent formulation of the Fan-Raspaud Conjecture and related problems, On the Chvátal rank of linear relaxations of the stable set polytope, TSP on Cubic and Subcubic Graphs, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, On two consequences of Berge–Fulkerson conjecture, Fractional covers for forests and matchings, On Compatible Normal Odd Partitions in Cubic Graphs, IFORS' Operational Research Hall of Fame Delbert Ray Fulkerson, Transversal matroid intersections and related packings, Energy of convex sets, shortest paths, and resistance, Unnamed Item, Unnamed Item, On the facial structure of set packing polyhedra, Line perfect graphs, Graphs with the Circuit Cover Property, Lifting the facets of zero–one polytopes, Unnamed Item, On the cycle polytope of a directed graph and its relaxations, (1,k)-configurations and facets for packing problems, Computing the clique number of \(a\)-perfect graphs in polynomial time, Berge-Fulkerson conjecture on certain snarks, Projective, affine, and abelian colorings of cubic graphs, S_12 and P_12-colorings of cubic graphs, Norms and perfect graphs, Clique-perfectness of complements of line graphs, Opposite Elements in Clutters, Ideal Clutters That Do Not Pack, On Sylvester Colorings of Cubic Graphs, 1‐Factor and Cycle Covers of Cubic Graphs, Dominants and submissives of matching polyhedra, A characterization of perfect graphs, Short cycle covers of graphs and nowhere-zero flows, Resistant Sets in the Unit Hypercube, Duality in mathematics and linear and integer programming, Integral decomposition in polyhedra, Finite checkability for integer rounding properties in combinatorial programming problems, On the use of penumbras in blocking and antiblocking theory, On a Conjecture of Fan and Raspaud, Integer Rounding for Polymatroid and Branching Optimization Problems, Circuit Double Covers of Graphs, Normal 5-edge-colorings of a family of Loupekhine snarks, Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming, Balanced matrices, Some facets of the simple plant location polytope, Fulkerson-covers of hypohamiltonian graphs, Polynomially bounded algorithms for locatingp-centers on a tree, On cliques associated to 3-set packing problems, Abelian Colourings of Cubic Graphs, Unions of perfect matchings in cubic graphs, Non-intersecting perfect matchings in cubic graphs (Extended abstract), Properties of vertex packing and independence system polyhedra, A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs, Packing rooted directed cuts in a weighted directed graph, Perfect zero–one matrices, Blocking and antiblocking sets, A note on the blocker of tours, Finite Solution Theory for Coalitional Games

Cites Work