| 求极大独立集的程序实现研究 |
| |
| 引用本文： | 李云,;傅秀芬,;何杰光,;林茜卡.求极大独立集的程序实现研究[J].微机发展,2008(9):64-67. |
| |
| 作者姓名： | 李云 ;傅秀芬 ;何杰光 ;林茜卡 |
| |
| 作者单位： | 广东工业大学计算机学院 |
| |
| 基金项目： | 广东省自然科学基金（07001802） |
| |
| 摘 要： | 独立集有着广泛的应用，尤其广泛应用于系统故障诊断领域。在求简单图极大独立集的程序实现方面，目前开展的研究工作还比较少。介绍简单图极大独立集的一种求取算法，剖析了该算法在使用面向对象程序设计模式中的实现方式，提出在定长字符串模式匹配中采用异或运算的运算法则来进行字符串模式匹配，由此作为多元式代数运算的基础对这个算法进行程序实现，并分析了这种字符串模式匹配的时间效率。
|
| 关 键 词： | 图 横式匹配 极大独立集 |
Procedures Research of Maximal Independent Sets |
| |
| LI Yun,FU Xiu-fen,HE Jie-guang,LIN Xi-ka.Procedures Research of Maximal Independent Sets[J].Microcomputer Development,2008(9):64-67. |
| |
| Authors: | LI Yun FU Xiu-fen HE Jie-guang LIN Xi-ka |
| |
| Affiliation: | LI Yun, FU Xiu-fen, HE Jie-guang, LIN Xi-ka (Faculty of Computer, Guangdong University of Technology, Guangzhou 510006, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | graph pattern matching maximal independent set |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
