基于树宽求解问题的高级工具和方法 - 扩展摘要
本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法,研究人工智能领域的几个已知问题,其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性,但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。
May, 2018
本文提出了一种基于数据库管理系统的通用框架来解决具有小分解树宽度的问数问题,利用动态规划在分解树上进行计算,并将 DP 算法实现到了一个 DBMS (PostgreSQL) 中。这是我们的实验室采用 DBMS 进行处理 TDs 算法的第一次尝试,我们的方法具有处理大型数据表,多核并行计算,以及中止计算等显而易见的优势。
Jan, 2020
本文结合分解性和后门集两种方法,研究了在与给定 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
本篇论文介绍了一种利用图形方法和动态规划结合已有的搜索求解器来解决定量推理问题的新系统,可以有效地处理 Answer Set Programming 方法中 epistemic logic programs 的复杂问题。
Aug, 2021
本文提出了一种基于内点法和树分解的线性规划问题求解算法,可以在近似相对误差为 ε 的情况下,在时间复杂度 Θ(n ⋅ tw² ⋅ log (1/ε)) 内求解给定的线性规划问题,其中 tw 是输入图的树宽,并且是第一个时间复杂度与子问题 Ax=b 的最快时间复杂度相匹配的算法。
Nov, 2020
该研究提出了一种通用框架,将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法,并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法,时间为 $ k^{O (1)}$ 双指数级。
May, 2022
本文研究了关于合取查询 (conjunctive queries) 的一些决策问题,发现针对无环或几乎无环查询的问题虽然一般来说是 NP 完全,但限制到这些查询中节点的树宽度和循环度是有界的,变得易于处理。针对查询的宽度这一最普遍的概念,我们证明没有多项式时间的算法可以高效地判断查询的宽度是否小于等于 k,而引入的超树分解概念和超树宽度则可以周旋这一难点,使得相应的问题变得可解。
Dec, 1998
本文介绍了一种从 SAT 到 normal ASP 的新型减少方法,并通过建立依赖图的循环长度(SCC 大小)与树宽之间所需的功能依赖性,以一种细粒度的方式刻画了硬度。
Jan, 2023
本文提出了一种基于分支界限算法的快速计算无向图树宽的算法 QuickBB,包括理论基础与算法实现,可以应用于任何无向图,并对该算法的实验结果进行了比较和分析。
Jul, 2012