parameterized complexity theory | BriefGPT

关键词parameterized complexity theory

搜索结果 - 5

从基于宽度的模型检查到基于宽度的自动定理证明
该研究提出了一种通用框架，将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法，并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法，时间为 $ k^{O (1)}$ 双指数级。
PDF2 years ago
基于本体的有界团宽数据库查询
本研究从参数复杂性角度研究了在有界团宽度的数据库上对本体中介查询 (OMQ) 的评估，研究了原子查询 (AQ)、连通查询 (CQ) 和连通查询的联合，发现所有 OMQ 问题都是固定参数线性 (FPL) 的，其参数是 OMQ 大小加上团宽度，
PDF2 years ago
IJCAIKemeny 排名聚合的多样性：参数化方法
研究表明，通过将方案多样性与参数化复杂性理论相结合，可以使用基于算法的框架解决实际相关问题，例如 Kemeny Rank 聚合问题。
PDF3 years ago
IJCAI有限置信推理的复杂性 - 无量词情况
本文研究在信念水平下进行推理的计算复杂性，并进行了参数化复杂性理论的进一步细化，探究信念水平和非逻辑符号数量对复杂性的影响。
PDF6 years ago
使用 FlowCutter 计算树分解：PACE 2017 提交
本文介绍了一个算法，该算法用于加速在道路图上最短路径计算的多层划分，展示了其如何融入到树分解和参数化复杂性理论中。该算法作为 Pace 2017 竞赛的参赛者之一，在启发式树分解计算赛道上解决了所有问题实例，并获得了亚军。
PDF7 years ago