\(b\)-matching degree-sequence polyhedra

DOI10.1007/BF01205074zbMath0758.05077OpenAlexW2029228217MaRDI QIDQ1180424

William H. Cunningham, Jan Green-Krótki

Publication date: 27 June 1992

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

polyhedraconvex hull\(b\)-matchingdegree sequencessubmodular functionsmin-max separation theorem

Mathematics Subject Classification ID

Linear inequalities of matrices (15A39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

A separation algorithm for the matchable set polytope, Discrete Fenchel duality for a pair of integrally convex and separable convex functions, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, An extension of the König-Egerváry property to node-weighted bidirected graphs, The membership problem in jump systems, Recent progress on integrally convex functions, The Orthant Non-Interaction Theorem for Certain Combinatorial Polyhedra and its Implications in the Intersection and the Dilworth Truncation of Bisubmodular Functions

Cites Work

• Unnamed Item
• Unnamed Item
• On T-joins and odd factors
• The polytope of degree sequences
• The perfectly matchable subgraph polytope of an arbitrary graph
• Matchings and \(\Delta\)-matroids
• Some combinatorial properties of discriminants in metric vector spaces
• Pseudomatroids
• Directed submodularity, ditroids and directed submodular flows
• The ellipsoid method and its consequences in combinatorial optimization
• On totally dual integral systems
• Extreme degree sequences of simple graphs
• The perfectly matchable subgraph polytope of a bipartite graph
• Greedy algorithm and symmetric matroids
• A greedy algorithm for solving a certain class of linear programmes