关键词: 超图; , 特殊超图; ,  最小边覆盖; , 分层算法; , MEC算法

Abstract: In this paper, the minimum edge covering problem of general hypergraphs and a class of special hypergraphs is investigated. The minimum edge covering problem of hypergraphs is a NP-hard problem. We design a layering algorithm to solve the problem, which the approximate ratio is reached $f$ and the time complexity is $O(km)$; then we provide two tight examples. The minimum edge covering problem of the special hypergraphs is solvable in polynomial time, and the strategy to solve the problem is: a corresponding root tree is firstly constructed, and then the tree traverses from down to up according to the level of each node with the dynamic programming, which based on the particularity of the root tree; MEC algorithm is designed for the minimum edge covering of special hypergraphs and the time complexity is $O({m^3})$.

Key words: Hypergraphs; , Special hypergraphs; , Minimize edge covering; , Layering algorithm; , MEC algorithm