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

边带权最大独立集问题及其近似算法 被引量：1

Edge Weighted Maximum Independent Set Problem and an Approximate Algorithm for it
下载PDF
导出
摘要 区别于传统对带权最大独立集问题的研完,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性。并且通过对问题结构的研完,给出了一个近似度为1/「(Δ′+1)/3」的近似算法,Δ′为图中点的最大度数。 Different from traditional research domain of Weighted Maximum Independent set Problem, in this paper, we firstly propose Edge Weighted Maximum Independent set Problem,give the formal definition and prove it is Np-Complete. Through researching the structure of problem,we give an approximate algorithm to solve it, which has the approximation ratio 1/[△′+1]/3], where △′ is the maximum degree of the vertex in graph G.
作者 张华 朱洪
机构地区 复旦大学计算机工程系智能信息处理实验室
出处 《计算机科学》 CSCD 北大核心 2004年第9期140-143,共4页 Computer Science
基金 科技部基金(No.2001CCA03000) 国家自然科学基金(No.60273045) 上海科学技术发展基金(No.025115032)
关键词 最大独立集 近似算法 最大度 证明 中点 度数 NP 问题结构 区别 角度 Weighted maximum independent set problem Edge weighted maximum independent set problem NP-complete Approximate algorithm
分类号 TP18 [自动化与计算机技术—控制理论与控制工程] O157 [自动化与计算机技术—控制科学与工程]
  • 相关文献

参考文献5

  • 1[1]Hochbaum D S. Approximation Algorithm for Np-hard Problem.PWS Publishing Company ,1997 被引量：1
  • 2[2]Corman T H,Leiserson C E,Rivest R L,Stein C. Introduction to Algorithms ,Second Edition,The MIT Press ,2001 被引量：1
  • 3[3]Arkin E M,Hassin R. On local search for weighted k-set packing.ESA′ 97 被引量：1
  • 4[4]Baker B S. Approximation algorithm for NP-complete problems on planar graphs. J. ACM, 1994 被引量：1
  • 5[5]Halldorsson M M,Lau H C. Low-degree graph partitioning via local search with applications to constraint satisfaction,max cut ,and3-coloring. J. Graph Algo. Applic. 1997 被引量：1

同被引文献20

  • 1Ziv J,Lempel A.A universal algorithm for sequential data compression[J].IEEE Trans on Information Theory,1977,23(3):337-343. 被引量：1
  • 2Christley S,Lu Y,Li C,et al.Human genomes as email attachments[J].Bioinformatics,2009,25(2):274-275. 被引量：1
  • 3Jung K,Yu N,Shin S,et al.A compressing method for genome sequence cluster using sequence alignment[C] //Proceedings of International Conference on Computer and Information Technology,Sydney,NSW,2008:520-525. 被引量：1
  • 4Chen X,Kwong S,Li M.A compression algorithm for DNA sequences and its applications in genome comparison[J].Genome Inform Ser Workshop Genome Information,1999,10:51-61. 被引量：1
  • 5Liu J Z,Yang J,Wang W.BiClustering in gene expression data by tendency[C] //Proceedings of International Conference on the Computational Systems Bioinformatics,Washington,2004:182-193. 被引量：1
  • 6Duda R,Hart E Pattern classification and scene analysis[M].New York:Wiley,1973. 被引量：1
  • 7Yang J,Wang W.CLUSEQ:Efficient and effective sequence clustering[C] //Proceedings of International Conference on Data Engineering,Bangalore,India,2003:101-112. 被引量：1
  • 8Guralnik V,Karypis G.A scalable algorithm for clustering sequential data[C] //Proceedings of IEEE International Conference on Data Mining,Washington,2001:179-186. 被引量：1
  • 9Morzy T,Wojciechowski M,Zakrzewicz M.Scalable hierarchical clustering method for sequences of categorical values[C] //Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining,Hong Kong,2001:282-293. 被引量：1
  • 10Huang Z.Extensions to the k-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge,1998,3(2):283-304. 被引量：1

引证文献1

计算机科学
2004年 第9期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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