大图中子图的可测性质

• 作者: 王正才 许道云 韦立
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 性质测试 询问复杂性 正则引理 正则归约 可测试性
• 年，卷（期）: 2012,（12）
• 所属期刊栏目: 人工智能
• 页码范围: 228-232
• 页数: 5页
• 分类号: TP301
• 字数: 8790字
• 语种: 中文

摘要

对于给定的距离参数ε,性质测试算法A需以高概率正确地区分给定的对象具备预定性质Ⅱ与ε-远离性质Ⅱ.若存在Ⅱ的测试算法A满足其询问复杂性独立于规模参数n,则称Ⅱ是可测的.设H是一个图,性质H-free为不含H-子图的图所构成的集合.在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质H-free是可测的[9].在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质H-free是可测的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与信息学院	125	460	12.0	16.0
2	韦立	贵州大学计算机科学与信息学院	9	43	4.0	6.0
3	王正才	贵州大学计算机科学与信息学院	5	54	3.0	5.0