网络图上的分段线性分式规划模型及有效算法

为了得到网络图上分段线性分式规划问题的有效算法，借助于线性规划问题的单纯形方法及网络图上修改支撑树的迭代方法，论证了一个基本可行解是否最优解的判别准则，并给出了网络图上分段线性分式规划问题的一个有效算法。为进一步解决网络图上非线性目标函数的优化问题提供了依据。     

连续属性朴素贝叶斯分类器的依赖扩展研究

针对朴素贝叶斯分类器不能有效利用属性之间依赖信息的问题,在将连续属性条件互信息计算、条件密度计算与通过建立类约束属性最大权重跨度树的父结点选择相结合的基础上,提出了连续属性朴素贝叶斯分类器选择性树结构依赖扩展方法.通过对比实验和分析,证实了扩展后分类器的分类准确率得到明显的改进.     

基于随机生成树的配电网重构模拟退火算法

提出了一种基于实数编码方式的配电网重构模拟退火算法,即按开关序号的实数编码方式产生随机序列,再利用图论方法产生对应的一棵生成树(一种树状网络结构)．该算法可保证解空间的可行性和完备性．对算法的邻域结构的确定进行了分析．给出的算例表明该算法求解快速,简单有效。     

一种支持QoS的多播路由算法

对支持QoS(服务质量)的多播路由技术作了较详细的分析,提出了一种后向搜索最小生成树算法作为有实时性要求的多播业务的路由算法,并模拟分析了该算法的优越性。     

一种基于功率控制的无线传感器网络跨层通信协议

提出一种新的跨层通信协议基于功率控制的定向生成树(PCDST).本协议采用定向生成树算法以解决数据传输过程中的无效能耗问题,并控制节点的传输功率以降低网络通信竞争强度.为了更好地控制传输功率这一关键因素,构建了一个网络效用最大化模型,并基于原始-对偶算法设计拉格朗日对偶函数,推导出传输功率的最优解集.这些跨层策略的应用能够使无线传感器网络在节能的同时保持良好的通信状态.仿真实验结果表明,本协议在节约能量和提高通信吞吐量方面具有很好的表现.     

稀疏图上有效的MST多边更新并行算法

ＭＳＴ（最小生成树ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ之略）多边更新（ｕｐｄａｔｉｎｇ）问题定义如下：给定一个赋权图Ｇ（Ｖ,Ｅ）和Ｇ的一棵最小生成树Ｔ（Ｖ,ＥＴ）,其中｜Ｖ｜＝ｎ,ＥＴ是树边集合,（１）给Ｇ添加Ｋ条新边,或者（２）在图Ｇ上改变Ｋ条边的权后重新为Ｇ寻找一棵最小生成树,１≤Ｋ＜ｎ．本文基于ＳＩＭＤＣＲＥＷＰＲＡＭ共享存贮模型,运用“进－退”策略,并把这一特殊手段与已有的平行算法组合起来,为一类稀疏图（｜Ｅ-ＥＴ｜＝Ｏ（Ｋ））找到了一种有效的ＭＳＴ多边更新算法．该算法需要Ｏ（ｌｏｇｎｌｏｇＫ）时间和Ｏ（ｍａｘ｛ｎ,ｕＫ／ｌｏｇｎｌｏｇＫ｝）处理机．     

我国股市行业间信息溢出的网络建模与实证研究

结合传统计量经济方法及复杂网络建模分析方法，实证研究了我国股市行业间的信息溢出关系及其影响因素、行业信息溢出能力及其分布.研究发现，收益率期限与行业间信息溢出效应强弱无关；市场因素显著增强了行业间的双向信息溢出效应，同时显著地减弱了单向信息溢出效应；随着市场行情的上涨(下跌)，行业间的信息溢出效应会相应地增强(减弱)；各行业的信息溢出能力呈现尖峰厚尾的分布；此外，最小生成树能够快速而有效地揭示股市行业间的信息溢出规律.     

网络中最优控制树问题的贪婪算法

最优控制树问题是大型通讯、交通和供销网络中的一类突出问题.以最小支撑树问题的贪婪算法为基础,分析了最优控制树的本质特征,得到了求网络中最优控制树的一种启发式算法,并给出了算例.     

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

The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding 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 pre-processed by reduction algorithm.     

完全二分图的生成树的个数

给出了生成子图的定义．证明了生成子图的构造定理和计数定理．提出了任意G（p,q）的生成树的计数方法和构造方法．介绍了完全二分图K3,3的生成树的计数和构造．