团宽和知识编译
本文证明了:如果基于一颗 treewidth 为 d 的图的量子电路中,其门控运算的总数为 T,则这个电路可以在 T^{O (1)}*exp [O (d)] 的时间里被确定性模拟。此外,本文还证明了:在施加到附近量子比特的约束下,可以高效地模拟对数深度电路。同时,如果随机选择资源并且基于 treewidth 很小的图,则 Raussendorf 和 Briegel 的 one-way 量子计算方案可以有效地被模拟。
Nov, 2005
该研究提出了一种通用框架,将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法,并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法,时间为 $ k^{O (1)}$ 双指数级。
May, 2022
本文主要研究了基于逻辑的问题及基于 treewidth 的方法和工具,并提出了一种新类型的问题降解方法,其中问题为有界 treewidth 的量化布尔公式(QBF)。结果表明,treewidth 是设计现代求解器时应考虑的一项重要的测量标准。
Aug, 2022
本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法,研究人工智能领域的几个已知问题,其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性,但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。
May, 2018
本文结合分解性和后门集两种方法,研究了在与给定 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
本文研究了关于合取查询 (conjunctive queries) 的一些决策问题,发现针对无环或几乎无环查询的问题虽然一般来说是 NP 完全,但限制到这些查询中节点的树宽度和循环度是有界的,变得易于处理。针对查询的宽度这一最普遍的概念,我们证明没有多项式时间的算法可以高效地判断查询的宽度是否小于等于 k,而引入的超树分解概念和超树宽度则可以周旋这一难点,使得相应的问题变得可解。
Dec, 1998
本文表明,CNF 无法被编译成由原始图树宽参数化的固定参数大小的有序二元决策图(OBDD)。因此,我们为 OBDD 和 SDD 提供了参数化分离,并证明了所提出的下界还可以产生 OBDD 和 SDD 的古典(非参数化)分离。此外,我们还展示了对于 OBDD 的现有的最佳参数化上界实际上适用于关联图树宽参数化。
Aug, 2013
提出了一个通用的查询决策框架,基于计数模型的结构简单性,可以确定各种逻辑蕴涵问题(简称查询)的可决性,其中 Blumensath 的分区宽度作为一个特别强大的宽度度量提出,重点介绍存在规则的形式化,其中分区宽度的规则子域覆盖范式为一周围侧子域。
Apr, 2023
本文研究了绝对性集合编程中的困难问题,并提出了一种新的动态规划算法来解决一个图形参数问题,即带符号的团宽度(signed clique-width)
Jun, 2016