On a theorem of Lovász on covers in r-partite hypergraphs

DOI10.1007/BF01844843MaRDI QIDQ1924486zbMATH OpenFDO

Authors Ron Holzman, Michael Krivelevich, Ron Aharoni

Publication date 11 March 1997

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

covershypergraphsmatching

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15)

Review text

A theorem of Lovász on covers in \(r\)-partite hypergraphs is generalized.

Cites work

• Approximate Set Covering in Uniform Hypergraphs
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• Matchings and covers in hypergraphs
• On the ratio of optimal integral and fractional covers
• Two combinatorial covering theorems

Cited in

(13)

• On approximation of the vertex cover problem in hypergraphs
• Approximation algorithms for hitting subgraphs
• Hypergraph representation via axis-aligned point-subspace cover
• Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
• Approximating vertex cover in dense hypergraphs
• The feedback arc set problem with triangle inequality is a vertex cover problem
• Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
• Approximating the discrete time-cost tradeoff problem with bounded depth
• Approximating the discrete time-cost tradeoff problem with bounded depth
• Approximate hypergraph vertex cover and generalized Tuza's conjecture
• Hypergraph representation via axis-aligned point-subspace cover
• A randomized rounding approach for DAG edge deletion
• Independence-domination duality

This page was built for publication: On a theorem of Lovász on covers in \(r\)-partite hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924486)