超图上最小边覆盖问题的算法研究

本文研究边赋权超图以及边赋权拉米纳(Laminar)超图的最小边覆盖问题.边赋权超图最小边覆盖问题是一个NP难问题,本文设计分层算法求解该问题,达到f近似比,及时间复杂度O(rm),其中f表示在超图的边集中出现最多顶点的次数,r表示超图的导出子图个数,m表示超图的边数.同时给出该算法的紧例子.而在边赋权拉米纳超图上求最小边覆盖问题是多项式时间可解的,求解该问题的策略是:首先构造对应的有根树,然后利用有根树的特殊性,基于动态规划的思想,对树从下往上按层次遍历各节点,设计MEC算法得到边赋权拉米纳超图上的最小边覆盖,求解该问题的时间复杂度为O(m^(3)).

基于点权约束的模糊最小权边覆盖问题研究

图论中的边覆盖问题由于其广泛的实际应用性,近年来受到广泛的关注。为求解基于点权约束的模糊最小权边覆盖问题首先提出Cons-模糊期望最小权边覆盖模型和Cons-模糊α-最小权边覆盖模型;随后设计一种结合模糊模拟技术和遗传算法的混合智能算法求解所提出的决策模型,并在混合智能算法中纳入点权约束因子;最后用一个数值试验验证混合智能算法和决策模型的有效性。

图的最小覆盖的逻辑算法

给出了利用命题逻辑公式的析取范式和主析取范式求图的全部极小覆盖和最小覆盖以及全部极小边覆盖和最小边覆盖的一般算法.