Relaxations of vertex packing

DOI10.1016/0095-8956(86)90087-0zbMath0596.05052OpenAlexW2012937096MaRDI QIDQ1078206

Martin Grötschel

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/10059

zbMATH Keywords

algorithmgraphupper boundvertex packing polytopeweighted independence number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (30)

An exact algorithm for the maximum stable set problem ⋮ Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Completing bases in four dimensions ⋮ On box totally dual integral polyhedra ⋮ Information theoretic parameters of noncommutative graphs and convex corners ⋮ Faithful orthogonal representations of graphs from partition logics ⋮ Semidefinite programming in combinatorial optimization ⋮ Complementation in T-perfect graphs ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022 ⋮ On claw-free \(t\)-perfect graphs ⋮ Roots and (Re)sources of Value (In)definiteness Versus Contextuality ⋮ Perfect couples of graphs ⋮ A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs ⋮ The generalized vertex cover problem and some variations ⋮ Sandwich theorems and capacity bounds for non-commutative graphs ⋮ A polyhedral study of the generalized vertex packing problem ⋮ A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming ⋮ A characterization of the weighted Lovász number based on convex quadratic programming ⋮ Semi-definite programming and quantum information ⋮ Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting ⋮ Probabilistic refinement of the asymptotic spectrum of graphs ⋮ Orthogonal representations and connectivity of graphs ⋮ The problem of quantum correlations and the totalitarian principle ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming ⋮ Stable sets and polynomials ⋮ The maximum clique problem ⋮ Entropy splitting for antiblocking corners and perfect graphs

Cites Work

• Polytope des independants d'un graphe série-parallèle
• The ellipsoid method and its consequences in combinatorial optimization
• On certain polytopes associated with graphs
• Normal hypergraphs and the perfect graph conjecture
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• On the Shannon capacity of a graph
• Blocking and anti-blocking pairs of polyhedra
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relaxations of vertex packing