fixed-parameter tractable | BriefGPT

关键词fixed-parameter tractable

搜索结果 - 5

利用树宽及其限制条件解决投影模型计数问题
本文介绍了一种新算法来解决投影模型计数（PMC）问题，该算法利用输入实例的原始图的小树宽，并在同时考虑了指标化的树宽有理论下限的情况下，提供固定参数可解，通过使用嵌套动态规划，并在数据库技术的帮助下，可以解决树宽上限超过 200 的实例的
PDFa year ago
计算与背景知识相一致的马尔可夫等价有向无环图数量
本文研究的问题是，在部分边缘方向已知的情况下，如何计算马尔科夫等价类中有向无环图的数量。我们发现，这个问题在一个有趣的实例类中是可固定参数可解的，因为我们建立了一个计数算法，它所需要的时间是该图大小的多项式，其次数不依赖于作为输入提供的附加
PDF2 years ago
关于 Answer-Set 编程的 Clique-Width 与有向宽度测量
本文研究了绝对性集合编程中的困难问题，并提出了一种新的动态规划算法来解决一个图形参数问题，即带符号的团宽度（signed clique-width）
PDF8 years ago
稀疏图上的重构
本研究针对两种古典的顶点子集问题 ISR 和 DSR，研究其重配置变体问题，同时提出一种固定参数可跟踪的算法来解决 ISR 和 DSR 问题。
PDF9 years ago
AAAI有限规划的完整参数化复杂度分析
该论文研究了参数化复杂性下命题性规划问题的分类，重点关注了解决方案计划的长度参数和常见的句法限制，包括 PUBS 限制和条件 / 效果数量限制，并确定哪些问题适用于多项式内核，哪些不适用。
PDF11 years ago