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

偶图求最小覆盖的一种算法 被引量：2

Minimum Covering Algorithm on Bipartite Graph
下载PDF
导出
摘要 以Konig定理作为理论基础,分析偶图的任一最大匹配的饱和顶点集与其任一最小覆盖的关系,得出偶图的任一最小覆盖都包含在该偶图的任一最大匹配的饱和顶点集中的结论。并利用此结论寻求到从偶图的非饱和顶点出发,利用偶图最大匹配求出偶图最小覆盖的一种算法。 On the basis of Konig theorem, the relations between the vertices set ot M-saturated （M is any maximum matching set of a bipartite graph G） and any minimum covering set of a bipartite graph G, were analyzed. The conclusion was found that in a bipartite graph G any minimum covering set was included in the vertices set which is M-saturated. Then harnessing the conclusion to find a algorithm that starting from the vertices of M-unsaturated and utilizing any maximum matching set M can find one of its minimum covering set in a bipartite graph.
作者 张秀梅
机构地区 辽宁工学院数理科学系
出处 《辽宁工学院学报》 2007年第2期132-135,共4页 Journal of Liaoning Institute of Technology(Natural Science Edition)
基金 辽宁省教育厅科研计划资助项目(05L187)
关键词 偶图 最大匹配 最小覆盖 Konig定理 多项式时间算法 bipartite graph maximum matching minimum covering Konig theorem polynomial time algorithm
分类号 O157 [理学—基础数学]
  • 相关文献

参考文献3

二级参考文献20

  • 1[1]Adleman L M. Molecular computation of solution to combinatorial problems[J]. Science 1994,266:1021～1024.
  • 2[2]Lipton R J. DNA solution of hard computational problem[J]. Science 1995, 268, 542～545.
  • 3[3]Ouyang Q, Kaplan P D, Liu S, Libchaber A. DNA solution of the maximal clique problem[J]. Science 1997,278,446～449.
  • 4[4]Smith L M, Corn R M, Condon A E, Lagally M G, Frutos A G, Liu Q, Thiel A J. A surface-based approach to DNA computation[J]. J. Comput. Biol. 1998,5(2), 255～267.
  • 5[5]Liu Q, Wang L, Frutos A G, Condon A E, Corn R M, Smith L M. DNA computing on surfaces[J]. Nature 2000, 403,175～179.
  • 6[6]Haoyang Wu. An improved surface-based method for DNA computation[J]. Biosystem, 2001,59:1～5.
  • 7[7]Bondy J A & Murty U S R. Graph theory with application[M]. Macmillan Press Ltd, 1976.
  • 8Adleman L. Molecular Computation of Solution to Combinatorial Problems[J]. Science, 1994,266 (11):1021-1024.
  • 9Gibbons A. Algorithmic Graph Theory[M]. Cambridge University Press, Cambridge, London,1985.
  • 10Lipton Richard J. DNA Solution of Computation Problems[J]. Science, 1995,268(4):542-545.

共引文献11

同被引文献14

  • 1Lu LM, Wang RS, Li WG. A target detection method in range-Doppler domain from SAR Echo data. Proc. of the 16th Int' l Conf. on Pattern Recognition (ICPR). 2002,1:91 - 94.
  • 2Dharwadker A. The Vertex Cover Algorithm. 2006. http://www.geocities.com/dharwadker/vertex_cover/.
  • 3Bondy J A,Murty U S R.图论及其应用[M].吴望名,李念祖译.北京:科学出版社,1984.
  • 4PATTIPATI K R,RAGHAVAN V,SHAKERI M,et al.TEAMS:testability engineering and maintenancesystem[C]//Proceedings of the American Control Conference,1994(2):1989-1995.
  • 5LUO J,PATTIPATI K R,QIAO L,et al.An integrated diagnostic development process for automotiveengine control systems[J].IEEE Transactions on Systems,Man,and Cybernetics-part C:Applications andReviews,2007,37(6):1163-1173.
  • 6TU F,PATTIPATI K R,DEB S,et al.Computationally efficient algorithms for multiple fault diagnosisin large graph-based systems[J].IEEE Transactions Systems,Man,Cybernetics-part A:Systems,Humans,2003,33(1):73-85.
  • 7SRIVASTAVA A N,MAH R W,MEYER C.Integrated vehicle health management technical plan,(version 2.03)[R].NASA Aeronautics Research Mission Directorate Aviation Safety Program,2009.
  • 8BLANKE M,KINNAERT M,LUNZE J,et al.Diagnosis and fault-tolerant control[M].Springer-Verlag,2006.
  • 9LIU Q,PROKHOROV D V,et al.Dynamic set-covering for real-time multiple fault diagnosis[C].2008IEEE Aerospace Conference,2008.
  • 10黄琪伟,刘健.配电网模式化接线优化规划[J].电力系统自动化,2008,32(7):73-77. 被引量：8

引证文献2

二级引证文献5

辽宁工学院学报
2007年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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