广西师范大学学报（自然科学版） ›› 2011, Vol. 29 ›› Issue (1): 38-42.

• • 上一篇    下一篇

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

韦立, 许道云, 王晓峰   

  1. 贵州大学计算机科学与信息学院,贵州贵阳550025
  • 收稿日期:2010-11-10 发布日期:2018-11-16
  • 通讯作者: 许道云(1959—),男,贵州安顺人,贵州大学教授,博导。E-mail: dyxu@gzu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(60863005,61011130038)

Hardness Analysis of Two Parameterization Counting Matching Problems

WEI Li, XU Dao-yun, WANG Xiao-feng   

  1. College of Computer Science and Information,Guizhou University,Guiyang Guizhou 550025,China
  • Received:2010-11-10 Published:2018-11-16

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

关键词: 参数化, 计数匹配问题, 固定参数易解, 随机近似方案

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

Key words: parameterization, counting matching problem, fixed-parameter tractable, randomized approximation scheme

中图分类号: 

  • TP301
[1] GROHE M.The parameterized complexity of database queries[C]//Proceeding of the 20th ACM Symposium on Principles of Data Systems.New York:ACM Press,2001:82-92.
[2] PAPADIMITRIOU C H,YANNAKAKIS M.On the complexity of database queries[C]//Proceeding of the 17th ACM Symposium on Principles of Data Systems.NewYork:ACM Press,1997:12-19.
[3] GOTTLOB G,LEONE N,SIDERI M.Fixed-parameter complexity in AI and nonmonotonic reasoning[C]//Logic Programming and Nonmonotonic Reasoning:LNCS Volume 1730.Berlin:Springer,1999:1-18.
[4] DOENEY R G,FELLOWS M R.Parameterized complexity[M].Berlin:Springer,1999.
[5] ARORA S,BARAK B.Computational complexity:a modern approach[M].Cambridge:Cambridge University Press,2009.
[6] VALIANT L G.The complexity of computing the permanent[J].Theoretical Computer Science,1979,8(2):189-201.
[7] TODA S.PP is as hard as the polynomial-time hierarchy[J].SIAM Journal on Computing,1991,20(5):865-877.
[8] JERRUM 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.
[9] VAZIRANI V V.Approximation algorithms[M].Berlin:Springer,2001.
[10] FLUM J,GROHE M.The parameterized complexity of counting problems[J].SIAM Journal on Computing,2004,33(4):892-922.
[11] FLUM J,GROHE M.Parameterized complexity theory[M].Berlin:Springer,2006.
[1] 许伦辉,黄宝山,钟海兴. AGV系统路径规划时间窗模型及算法[J]. 广西师范大学学报（自然科学版）, 2019, 37(3): 1-8.
[2] 石亚冰, 黄予, 覃晓, 元昌安. 基于优化初始种子新策略的K-Means聚类算法[J]. 广西师范大学学报（自然科学版）, 2013, 31(4): 33-40.
[3] 翁世洲, 吕跃进, 莫京兰. 基于优势关系的排序模型及其保序性约简理论[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 37-44.
[4] 曹永春, 邵亚斌, 田双亮, 蔡正琦. 一种基于免疫遗传算法的聚类方法[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 59-64.
[5] 张超群, 郑建国, 李陶深. 侦察蜂在人工蜂群算法中的作用[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 72-80.
[6] 周艳聪, 顾军华, 董永峰. 逆向二进制防碰撞算法及其FPGA硬件实现[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 94-99.
[7] 谢光强, 章云, 李杨, 曾启杰. 基于Krause多智能体一致性模型的研究[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 106-113.
[8] 黄敏, 靳婷, 钟声, 马玉春. 基于改进蚁群算法求解连续空间寻优问题[J]. 广西师范大学学报（自然科学版）, 2013, 31(2): 34-38.
[9] 翟莹, 易忠, 谢正卫, 邓培民, 李王月. 一类特殊规则的二维混合元胞自动机的GOE问题[J]. 广西师范大学学报（自然科学版）, 2013, 31(1): 37-43.
[10] 崔耀东, 周密, 杨柳. 多线材一维下料问题的求解策略[J]. 广西师范大学学报（自然科学版）, 2012, 30(3): 149-153.
[11] 马宁, 于洪志. 基于Arnold变换和DCT变换的图像水印算法[J]. 广西师范大学学报（自然科学版）, 2011, 29(3): 163-167.
[12] 叶青, 黄强, 聂斌, 李欢. 一种自适应的高维离群点识别方法[J]. 广西师范大学学报（自然科学版）, 2020, 38(2): 107-114.
[13] 王俊杰, 温雪岩, 徐克生, 于鸣. 基于局部敏感哈希的改进堆叠算法[J]. 广西师范大学学报（自然科学版）, 2020, 38(4): 21-31.
[14] 韦振汉, 宋树祥, 夏海英. 基于随机森林的锂离子电池荷电状态估算[J]. 广西师范大学学报（自然科学版）, 2018, 36(4): 27-33.
[15] 鄂旭, 邵良杉, 李胜, 王全铁. 一种基于关联度的区间型数据离散化方法[J]. 广西师范大学学报（自然科学版）, 2011, 29(2): 134-137.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发