本文结合分解性和后门集两种方法,研究了在与给定CNF公式相关联的图的树宽不超过t的CNF公式集合W_t中找到一个小的强后门集的算法问题。我们证明了:1.找到大小不超过2^k的强W_t后门集,或确定F没有大小不超过k的强W_t后门集;2.找到CNF公式F的满足分配数量或确定sb_t(F)> k的算法,其中sb_t(F)表示F的最小强W_t后门集的大小。
Apr, 2012
本文研究图形单元中结构的限制及其与推理难度之间的关系,发现较低的树宽是确保推理可行性的唯一结构限制,即使是最优情况下的图结构,也不存在多项式时间复杂度的推理算法。
Jun, 2012
本文提出了一种基于分支界限算法的快速计算无向图树宽的算法QuickBB,包括理论基础与算法实现,可以应用于任何无向图,并对该算法的实验结果进行了比较和分析。
Jul, 2012
通过证明经过单次读取分支程序(nrobp)的空间下限为n^Ω(k),针对原始图的树宽不超过k的cnfs可证明nrobp的固定参数空间复杂性不可行,在此基础上我们得到自由二元决策图和决策可分解否定正常形式之间的近多项式分离。
Nov, 2014
本文研究了绝对性集合编程中的困难问题,并提出了一种新的动态规划算法来解决一个图形参数问题,即带符号的团宽度(signed clique-width)
Jun, 2016
本文探讨抽象论证中关于扩展项的计数和投影模型计数,提出了一种基于动态规划的新算法,并建立了经典和参数化的复杂度结果,考虑到评估参数化问题的树宽度,最后针对有界树宽算法建立下界,得出复杂度分析结论。
Nov, 2018
本文提出了基于面积凸性的混合装箱问题LP的宽度相关算法并进一步将其应用于最密子图问题中,实现了比宽度独立算法更高的精度。
Sep, 2019
本文研究了二元约束满足问题 (BINARY-CSPs) 的多种推广的复杂性及参数化复杂性,探讨了基于半环的代数方法,提出了组件双宽属性的 generalization。研究表明,在受限制的条件下,该方法在多种问题中取得了优秀算法复杂度上界。
Jul, 2022
介绍了树宽和超树宽的概念,并通过计算阈值树宽和超树宽,提出了一种固定参数算法,可在多项式时间内解决 CSP 问题。
Oct, 2022
提出了一个通用的查询决策框架,基于计数模型的结构简单性,可以确定各种逻辑蕴涵问题(简称查询)的可决性,其中Blumensath的分区宽度作为一个特别强大的宽度度量提出,重点介绍存在规则的形式化,其中分区宽度的规则子域覆盖范式为一周围侧子域。
Apr, 2023