数学理论与应用 ›› 2021, Vol. 41 ›› Issue (4): 109-.
• • 上一篇 下一篇
林雯 王嘉宝* 陈智斌
出版日期:
发布日期:
通讯作者:
基金资助:
Online:
Published:
摘要: 本文研究一般超图以及一类特殊超图上的边赋权最小边覆盖问题,超图上最小边覆盖问题是一个NP难问题,本文设计分层算法求解该问题,达到$f$近似比且时间复杂度为$O(km)$,同时给出了该算法的紧例子.而在一类特殊超图求最小边覆盖问题是多项式时间可解的,求解该问题的策略是:首先构造对应的有根树,然后利用有根树的特殊性,基于动态规划的思想,对树从下往上按层次遍历各节点,设计MEC算法得到特殊超图上的最小边覆盖,求解该问题的时间复杂度为$O({m^3})$.
关键词: 超图; , 特殊超图; , 最小边覆盖; , 分层算法; , 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
林雯 王嘉宝 陈智斌. 针对超图上最小边覆盖问题的算法研究[J]. 数学理论与应用, 2021, 41(4): 109-.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://mta.csu.edu.cn/CN/
http://mta.csu.edu.cn/CN/Y2021/V41/I4/109