LP duality in infinite hypergraphs

DOI10.1016/0095-8956(90)90098-KzbMath0727.05048MaRDI QIDQ803165

Ron Aharoni, Ran Ziv

Publication date: 1990

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

zbMATH Keywords

fractional coverfractional matchingcomplementary slackness conditions of linear programmingGallai's theoremstrong duality property

Mathematics Subject Classification ID

Linear programming (90C05) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Strong LP duality in weighted infinite bipartite graphs ⋮ A note on the minimum size of matching-saturated graphs ⋮ Optimal fractional matchings and covers in infinite hypergraphs: existence and duality ⋮ Infinite matching theory ⋮ On packing and covering polyhedra in infinite dimensions

Cites Work

• A generalization of Tutte's 1-factor theorem to countable graphs
• Maximal tight sets and the Edmonds-Gallai decomposition for matchings
• Menger's theorem for countable graphs
• Matchings in infinite graphs
• Fractional matchings and covers in infinite hypergraphs
• Injective choice functions for countable families
• 2-Matchings and 2-covers of hypergraphs
• König's Duality Theorem for Infinite Bipartite Graphs