期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

Hardness Analysis of Two Parameterization Counting Matching Problems
下载PDF
导出
摘要 匹配计数问题是一个著名的难问题,考虑它的两个参数化问题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.
作者 韦立 许道云 王晓峰
机构地区 贵州大学计算机科学与信息学院
出处 《广西师范大学学报（自然科学版）》 CAS 北大核心 2011年第1期38-42,共5页 Journal of Guangxi Normal University:Natural Science Edition
基金 国家自然科学基金资助项目(60863005 61011130038)
关键词 参数化 计数匹配问题 固定参数易解 随机近似方案 parameterization counting matching problem fixed-parameter tractable randomized approximation scheme
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献11

  • 1GROHE M. The parameterized complexity of database queries[C]//Proeeeding of the 20th ACM Symposium on Prin ciples of Data Systems. New York : ACM Press, 2001 . 82-92.
  • 2PAPADIMITRIOU C H, YANNAKAKIS M. On the complexity of database queries [C]//Proceeding of the 17th ACM Symposium on Principles of Data Systems. New York :ACM Press, 1997 : 12-19.
  • 3GOTTLOB G,LEONE N,SIDERI M. Fixed-parameter complexity in AI and nonmonotonie reasoning [C]//Logie Programming and Nonmonotonic Reasoning : LNCS Volume 1730. Berlin :Springer, 1999 : 1-18.
  • 4DOENEY R G ,FELLOWS M R. Parameterized complexity[M].Berlin:Springer, 1999.
  • 5ARORA S,BARAK B. Computational complexity; a modern approach[M]. Cambridge :Cambridge University Press, 2009.
  • 6VALIANT L G. The complexity of computing the permanent[J]. Theoretical Computer Science, 1979,8(2):189-201.
  • 7TODA S. PP is as hard as the polynomial-time hierarchy[J].SIAM Journal on Computing, 1991,20(5) :865-877.
  • 8JERRUM M ,SINCLAIR A,VOGODA E. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries[J]. Journal of the ACM, 2004,51 (4) : 671-697.
  • 9VAZIRANI V V. Approximation algorithms[M]. Berlin : Springer, 2001.
  • 10FLUM J ,GROHE M. The parameterized complexity of counting problems[J]. SIAM Journal on Computing, 2004,33 (4) :892-922.
广西师范大学学报（自然科学版）
2011年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部