A new algorithm for degree-constrained minimum spanning tree based on the reduction technique

来源 :自然科学进展(英文版) | 被引量 : 0次 | 上传用户:zlp_dream
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
The degree-constrained minimum spanning tree (DCMST) is an iVP-hard problem in graph theory. It consists of rinding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been preprocessed by reduction algorithm.
其他文献
H antigen, the precursor of A and B antigens, belongs to Hh blood system in which it is the only antigen. H antigen distributes on all the human RBC surface exc
大豆疫霉菌(Phytophthora sojae)是疫霉菌中难在培养条件下形成孢子囊的菌种之一.对诱发大豆疫霉菌产生游动孢子囊的10种方法进行比较研究,结果表明,供试的10种方法除了MSS溶
目的 研究启动子和衰减子突变与大肠埃希菌高产AmpC酶的关系.方法 4株大肠埃希菌临床分离株AmpC启动子克隆到报告质粒pCAT3 basic vector氯霉素乙酰转移酶(CAT)基因上游,用测
兴建塞文河口潮汐发电工程将有助于英国实现其碳减排的目标,并为其提供5%的电力需求。基于工程费用、规模、发电量及潜在影响,最终筛选出加的夫-韦斯顿工程和舒特斯工程两个
计算机和网络信息技术的迅速发展,使网络成瘾这个新的社会问题越来越受到人们的广泛关注和重视,如何帮助人们远离网络成瘾的困扰,成为近年来国内外学者的研究热点,综述国内外
关于因人类耗用行为而导致可再生资源灭绝的理论研究,应该以个体理性下的短期利益最大化为假定.通过构建此类模型,对珍贵可再生自然资源的灭绝问题进行了探讨.可再生资源的再
随着城市竞争的加剧和城市政府职能的转变,提出了城市经营是我国实现城市可持续发展的有效选择.从城市经营思想的萌芽、背景、内容及实证研究成果几个方面,对国内外研究状况
By using DDRT-PCR and EST segment ligation, a novel mouse thymus involution related gene Rwddl was identified. The reading frame encoded a protein of 243 amino
以高产杂交稻组合两优培九和国稻6号为材料,设置基肥:分蘖肥:穗肥比例分别为50:30:20,60:10:30和40:20:40的不同氮肥管理,研究了强化栽培(SRI)条件下不同氮肥运筹对土壤微生
The quantity of soil microbes and the structure of ammonium oxidizing bacterial (AOB) community were analyzed using the dilution plate counting and most probabl