Properties of vertex packing and independence system polyhedra

DOI10.1007/BF01580222zbMath0281.90072OpenAlexW2075339720MaRDI QIDQ4766816

Nemhauser, George I., Leslie E. jun. Trotter

Publication date: 1974

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

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10)

Related Items

More complete intersection theorems, Vertex packing problem application to the design of electronic testing fixtures, A Faster Parameterized Algorithm for Group Feedback Edge Set, A capacitated hub location problem under hose demand uncertainty, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, Fixed interval scheduling: models, applications, computational complexity and algorithms, New facets for the two-stage uncapacitated facility location polytope, Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem, Alternative formulations for the set packing problem and their application to the winner determination problem, Complexity of searching an immobile hider in a graph, On ternary problems, On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\), On the 0,1 facets of the set covering polytope, A generalization of antiwebs to independence systems and their canonical facets, On the facial structure of the set covering polytope, On cutting-plane proofs in combinatorial optimization, Sparse obstructions for minor-covering parameters, Facets and lifting procedures for the set covering polytope, The stable set problem: clique and nodal inequalities revisited, \(O(n \log n)\) procedures for tightening cover inequalities, Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model, Complementation in T-perfect graphs, Strong formulation for the spot 5 daily photograph scheduling problem, On the complete set packing and set partitioning polytopes: properties and rank 1 facets, 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, On fractional realizations of graph degree sequences, 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, Discrete extremal problems, 2-clique-bond of stable set polyhedra, On stable set polyhedra for K//(1,3)free graphs, Vertex packings: Structural properties and algorithms, Faces for a linear inequality in 0–1 variables, Facet of regular 0–1 polytopes, On the facets of lift-and-project relaxations under graph operations, Adding incompatibilities to the simple plant location problem: formulation, facets and computational experience, Facets of the knapsack polytope, Handelman's hierarchy for the maximum stable set problem, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, Typical performance of approximation algorithms for NP-hard problems, Fixed cardinality stable sets, Cutting planes from extended LP formulations, Crown reductions for the minimum weighted vertex cover problem, Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph, On the mixed set covering, packing and partitioning polytope, On tightening cover induced inequalities, The generalized independent set problem: polyhedral analysis and solution approaches, The complexity of lifted inequalities for the knapsack problem, Efficient stabilization of cooperative matching games, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, Further facet generating procedures for vertex packing polytopes, Polyhedral results for the precedence-constrained knapsack problem, Cutting planes in integer and mixed integer programming, A class of facet producing graphs for vertex packing polyhedra, A polyhedral study of the generalized vertex packing problem, On \(f\)-domination: polyhedral and algorithmic results, Polyhedral properties of the induced cluster subgraphs, Lifting the facets of zero–one polytopes, Hitting Forbidden Minors: Approximation and Kernelization, On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\), (1,k)-configurations and facets for packing problems, Approximability of clique transversal in perfect graphs, Optimizing over pure stationary equilibria in consensus stopping games, Ehrhart series of fractional stable set polytopes of finite graphs, Extended formulations for vertex cover, Optimization algorithms for the disjunctively constrained knapsack problem, Gear composition and the stable set polytope, Minimum partition of an independence system into independent sets, Valid inequalities and facets of the capacitated plant location problem, Single machine precedence constrained scheduling is a Vertex cover problem, An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., Fractional matroid matchings, Matchings and covers in hypergraphs, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope, Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics, Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope, Facets and algorithms for capacitated lot sizing, Valid inequalities, cutting planes and integrality of the knapsack polytope, Strong and weak edges of a graph and linkages with the vertex cover problem, A New Facet Generating Procedure for the Stable Set Polytope, Stable sets, corner polyhedra and the Chvàtal closure, A new lifting theorem for vertex packing, A polyhedral approach to sequence alignment problems, Tractability of König edge deletion problems, Worst-case analysis of clique MIPs, On the facets of the simple plant location packing polytope, Dynamic node packing, On certain classes of fractional matchings, Nearly optimal robust secret sharing against rushing adversaries, The complexity of facets (and some facets of complexity), Some facets of the simple plant location polytope, Erratum to ``Comparison of column generation models for channel assignment in cellular networks, The maximum clique problem, Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm, A cutting plane method for solving harvest scheduling models with area restrictions, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles, Light on the infinite group relaxation. I: Foundations and taxonomy, Estimating the Size of Branch-and-Bound Trees, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover, Lifting for the integer knapsack cover polyhedron, New variants of the simple plant location problem and applications, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, On the minimum \(s-t\) cut problem with budget constraints, A theoretical and computational analysis of full strong-branching, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, What Is Known About Vertex Cover Kernelization?, Unnamed Item, Unnamed Item, Transitive packing, A tutorial on branch and cut algorithms for the maximum stable set problem, New facets for the set packing polytope, Extreme points of discrete location polyhedra, Comparison of column generation models for channel assignment in cellular networks, Upper and lower bounds on approximating weighted mixed domination, Triangle packing in (sparse) tournaments: approximation and kernelization, On a Conjecture of Nagy on Extremal Densities, Unnamed Item

Cites Work