计算机科学 ›› 2014, Vol. 41 ›› Issue (8): 122-124.doi: 10.11896/j.issn.1002-137X.2014.08.027
• 2013年全国理论计算机科学学术年会 • 上一篇 下一篇
刘坤良,张大坤,武继刚
LIU Kun-liang,ZHANG Da-kun and WU Ji-gang
摘要： 给定一棵树,树上的每个节点被赋予一对数值,它们分别表示节点的值和权重。基于权重约束的最大密度路径算法用于搜索树上的最大密度路径,即最大密度路径上所有节点的值之和与节点的权重之和的比值是所有路径中最大的。通过研究发现,现有的基于权重约束的最大密度路径算法有一定的局限性。文中提出了突破该局限性的可行性方案,进而设计并改进了基于权重约束的最大密度路径算法。
| [1] Hsieh Sun-yuan,Chou Ting-yu．The weight-constrained maxi-mum-density subtree problem and related problems in trees[J]．The Journal of Supercomputing,2010,54(3):366-380 [2] Lau H C,Ngo T H,Nguyen B N．Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics[J]．Discrete Optimization,2006(3):385-391 [3] Su H-H,Lu C L,Tang Chuan-yi．An improved algorithm for finding a length-constrained maximum-density subtree in a tree[J]．Information Processing Letters,2008(109):161-164 [4] Lin Rung-ren,Kuo W-H,Chao Kun-mao．Finding a Length-Constrained Maximum-Density Path in a Tree[J]．Journal of Combinatorial Optimization,2005,9:147-156 [5] Hsieh S-Y,Cheng C-S．Find a maximum-density path in a tree under the weight and length constrains[J]．Information Proces-sing Letters,2008(105):202-205 [6] Lin R R,Kuo W H,Chao K M．Finding a length-constrainedmaximum-density path in a tree[J]．Journal of Combinatorial Optimization,2005,9(2):147-156 [7] Chao K M．On computing all suboptimal alignments[J]．Information Sciences,1998,105:189-207 [8] Chao K M,Hardison R C,Miller W．Recent developments in linear-space alignment methods:A survey[J]．Journal of Computational Biology,1994,1:271-291 [9] Lin Y L,Jiang T,Chao K M．Algorithms for locating the length-constrained heaviest segments,with application to biomolecular sequences analysis[J]．Journal of Computer and System Sciences,2002,65(3):570-586 [10] Chung K M,Lu H I．An optimal algorithm for the maximum-density segment problem[J]．SIAM Journal on computing,2004(34):373-387 |
| No related articles found! |
|
||
首页