东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

两个参数化匹配计数问题的难度分析

期刊名称：广西师范大学学报·自然科学版,2009
时间：0
页码：38-42
语言：中文
分类：TP301[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
作者机构：[1]贵州大学计算机科学与信息学院,贵州贵阳550025
相关基金：国家自然科学基金资助项目（60863005 61011130038）
相关项目：命题公式有效推理的特殊变元集及算法研究

关键词：参数化, 计数匹配问题, 固定参数易解, 随机近似方案, parameterization, counting matching problem, fixed-parameter tractable, randomized approximation scheme

中文摘要：

匹配计数问题是一个著名的难问题,考虑它的两个参数化问题p-deg-#MATCHING与p-#MATCHING,证明了p-deg-#MATCHING是固定参数易解的,p-#MATCHING有固定参数易解随机近似方案。

英文摘要：

Counting matching problem is an intractable problem.Considering its corresponding parameterized problems p-deg-#MATCHING and p-#MATCHING,p-deg-#MATCHING is proved to be fixed-parameter tractable and p-#MATCHING has a randomized approximation scheme of fixed-parameter tractable.

同期刊论文项目