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

生成图的全部极大独立集的一般方法 被引量：4

A general method for generating all maximal independent sets of a graph
下载PDF
导出
摘要 图的极大独立集问题是图论中重要的NPC问题,独立集具有广泛的应用领域,如编码理论、信道分配、资源配置、纠错码理论等。文章运用拟序关系理论,系统研究了生成图的全部极大独立集的一般方法,该方法简单实用,程序化实现容易。 The problem of maximal independent sets of a graph is an important NP-complete problem in graph theory. The maximal independent set has a number of applications in areas such as coding theory, channel assignment, resource placement and error-correcting codes. In this paper, using the theory of quasi order relation, the general method for generating all maximal independent sets is given. The method is simple and practical and has been realized easily by a computer program.
作者 殷剑宏 汪荣贵 薛峰
机构地区 合肥工业大学计算机科学与信息学院
出处 《合肥工业大学学报（自然科学版）》 CAS CSCD 北大核心 2008年第3期479-483,共5页 Journal of Hefei University of Technology：Natural Science
基金 国家自然科学基金资助项目(60575023) 安徽省自然科学基金资助项目(070412054) 合肥工业大学科研基金资助项目(050507F)
关键词 图论 极大独立集 NP问题 拟序集 Hasse图 graph theory maximal independent set NP-problem quasi order set Hasse diagram
分类号 TP313 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献12

  • 1Jha P K. Smallest independent dominating sets in kronecker products of cycles[J]. Discrete Applied Mathematics, 2001, 113:303-306.
  • 2Haynes T W, Hedetniemi S T, Slater P T. Fundamentals of domination in graphs [M]. New York:Marcel-Dekker, 1998:20--80.
  • 3Jha P k, Slutzki G. A scheme to construct distance-three codes, with applications to the n-cube[J]. Inform Process Lett, 1995,55 : 123-127.
  • 4Pless V. Introduction to the theory of error-correcting codes [M]. 2nd ed. New York: Wiley, 1989:30-- 100.
  • 5Favaron O, Hedetniemi S M, Hedetniemi S T, et al. On k- dependent domination [J]. Discrete Mathematics, 2002, 249:83--94.
  • 6Rautenbach D. Bounds on the strong domination number [J]. Discrete Mathematics, 2000, 215 : 201-212.
  • 7张大方.基于矩阵的极大独立点集生成算法[J].电子学报,1998,26(5):86-88. 被引量：12
  • 8李有梅,徐宗本,苗夺谦.用神经网络启发式算法求解最大独立集问题[J].模式识别与人工智能,2003,16(1):76-80. 被引量：2
  • 9李有梅,徐宗本,孙建永.一类求解最大独立集问题的混合神经演化算法[J].计算机学报,2003,26(11):1538-1545. 被引量：9
  • 10Bollobds B. Modem graph theory[M]. Springer-Verlag, 2000 : 50-- 120.

二级参考文献25

  • 1李兢,刘长林,申石虎.关于图的极大独立集的理论及生成方法[J].电子学报,1995,23(8):78-79. 被引量：3
  • 2陈树柏，网络图论及其应用，1982年，176页
  • 3Shrivastava Y,Dasgupta S, Reddy S M. Guaranteed convergence in a class of Hopfield networks. IEEE Transactions on Neural Networks, 1992, 3(6): 951～961
  • 4Bondy J A, Murty U S R. Graph Theory with Applications. London: The Macmillan Press, 1976
  • 5Mazumadar P, Yih J S. Neural computing for built inself repair of embedded memory arrays. In: Proceedings of the 19th International Symposium on Fault Tolerant Computing, Chicago, USA, 1989. 480～487
  • 6Pramanick I. Parallel dynamic interaciton--An inherently parallel problem solving methodology[Ph D dissertation]. Department of ECE, University of Iowa, Iowa, USA, 1991
  • 7Wilf H S. The number of maximal independent sets in a tree. SIAM Journal of Algebraic Discrete Methods, 1986, 7(1): 125～130
  • 8Jou M J. The number of maximal independent sets in graphs[Master dissertation]. Department of Applied Mathematics, National Chiao Tung Center University, Taiwan, 1990
  • 9Jou M J. Counting independent sets[Ph D dissertation]. Department of Applied Mathematics, National Chiao Tung Center University, Taiwan, 1996
  • 10Jou M J,Chang G J. Maximal independent sets in graphs with at most one circle. Discrete Applied Mathematics, 1997, 79(1～3): 67～73

共引文献21

同被引文献21

  • 1LYNGSQ R,PEDERSEN C.RNA pseudoknot prediction in energybased models[J].Journal of Computational Biology,2000,7(3/4):409-427.
  • 2KATO Y,SEKI H,KASANU T.RNA structure prediction including pscudoknots based on stochastic multiple context-free grammar[J].IPSJ Transactions on Database,2006,47(SIG17):12-21.
  • 3ZUKER M,STIEGHR P.Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information[J].Nucleic Acids Research,1981,9(1):133-148.
  • 4RIVAS E,EDDY SR.A dynamic programming algorithm for RNA structure prediction including pseudoknots[J].Journal of Molecular Biology,1999,285(5):2053-2068.
  • 5DIRKS R M,PIERCE N A.A partition function algorithm for nucleic acid secondary structure including pseudoknots[J].Journal of Computational Chemistry,2003,24(13):1664-1677.
  • 6TSANG H H,WIESE K C.SARNA-Predict-pk:Predicting RNA secondary structures including pseudoknots[C]//CIBCB'08:Proceedings of the 2008 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology.Washington,DC:IEEE,2008:1-8.
  • 7LI HENGWU.Heuristic algorithm for pseudoknotted RNA structure prediction[C]//2008 Fourth International Conference on Natural Computation.Jinan:[s.n.],2008,676:542-546.
  • 8ROSEN K H.Discrete mathematics and its applications[M].4th ed.北京:机械工业出版社,2002:10-90.
  • 9XIA T,SANTALUCLA J,Jr.,BURKARD M E,et al.Thermodynamic parameters for an expanded nearest-neighbor model for forration of RNA duplexes with Watson-Crick base pair[J].Riochemistry,1998,37(42):14719-14735.
  • 10REEDER J,GIEGERICH R.Design,implementation and evaluation of a practical pseudoknot folding algorithm based on themodynamics[J].BMC Bioinfommtics,2004,5:104.

引证文献4

二级引证文献5

合肥工业大学学报（自然科学版）
2008年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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