Minimum size transversals in uniform hypergraphs

作者：Lonc Zbigniew^*; Warno Karolina

来源：Discrete Mathematics, 2013, 313(23): 2798-2815.

DOI：10.1016/j.disc.2013.08.022

• Minimum-sized transversal
• Transversal number
• Uniform hypergraph
• Turan type problems

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number tau(H) of a hypergraph His the minimum cardinality of a transversal in H. A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvatal and McDiarmid (1992) [3]) gave some upper bounds for tau(H) in a uniform hypergraph H with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for tau(H) which improve the bounds by Chvatal and McDiarmid.

• 出版日期2013-12-6