根据已知链图找出最大链图的有效的算法

• 作者: 刘佰军 赵慧 郑忠国
• 来源期刊: 中国科学A辑
• 学科: 数学
• 关键词: Markov图模型 链图 最大链图 被保护边
• 年，卷（期）: 2005,（10）
• 页码范围: 1188-1200
• 页数: 13页
• 分类号: O1
• 字数: 8831字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9232.2005.10.010

摘要

链图(CG)是Markov图模型的一个有效的处理工具.代表相同条件独立结构的链图称为Markov等价的.Frydenberg指出在等价的链图中存在一个包含其他所有等价链图的元素,称为最大链图.给出了一个根据已知链图找出最大链图的算法,计算复杂度仅为O(n3)(目前已有算法的复杂度约为O(n!)),从而给出了直观地判断一个链图是否是与之等价的最大链图的方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑忠国	北京大学数学科学学院	27	176	8.0	12.0
2	赵慧	北京大学数学科学学院	16	143	6.0	11.0
6	刘佰军	北京大学数学科学学院	2	4	1.0	2.0