求极大独立集的程序实现研究  

Procedures Research of Maximal Independent Sets

作　　者：李云[1] 傅秀芬[1] 何杰光[1] 林茜卡[1] 

机构地区：[1]广东工业大学计算机学院,广东广州510006

出　　处：《计算机技术与发展》2008年第9期64-67,共4页Computer Technology and Development

基　　金：广东省自然科学基金(07001802)

摘　　要：独立集有着广泛的应用,尤其广泛应用于系统故障诊断领域。在求简单图极大独立集的程序实现方面,目前开展的研究工作还比较少。介绍简单图极大独立集的一种求取算法,剖析了该算法在使用面向对象程序设计模式中的实现方式,提出在定长字符串模式匹配中采用异或运算的运算法则来进行字符串模式匹配,由此作为多元式代数运算的基础对这个算法进行程序实现,并分析了这种字符串模式匹配的时间效率。Independent sets share a wide range of applications, particularly widely used in the field of fault diagnosis system. In seeking maximal independent sets of a simple graph by procedures, ongoing research is also relatively small. Presents an algorithm for getting all the maximal independent sets of a simple graph. It detailed analysis of this algorithm in using object - oriented programming model and it proposes using XOR computing algorithm to carry out the string pattern matching in a fixed - length string pattern matching. Based on this,it programs for this algorithm through multi - algebraic operations. Finally, it analyzes the string pattern matching time complexity.

关 键 词：图 横式匹配 极大独立集 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]