网络中的最优控制树问题

众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.     

PACKING A TREE OF ORDER p WITH A （p,p＋1）—GRAPH

Let G1 and G2 be two graphs of the same order,If G1 is isomorphic to a spanning subgraph of the complement of G2,then we say that G1 and G2 are packable.A graph G is called a (p,m)-graph if G has p vertices and m edges.The main purpose of this paper is to present a necessary and sufficient condition for a tree of order p and a (p,p 1)-graph to be packable.     

OBSERVABILITY OF EXTENDED TIMED EVENT GRAPH

In this paper, we study some results of extended timed event graph (ETEG) by using graph theory's methods in the dioid framework. A necessary and sufficient condition for the observability of ETEG is obtained and ETEG's standard structure is also established.     

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.     

Petersen图中包含给定边集的最长圈及其在3－正则图中的应用

给出了Petersen图中包含给定边集的最长圈的结果及该结果在3-连通、3-正则图中的应用；最后提出两个问题。     

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题，介绍了一种基于竞争造就优化和决策左右结果的新型算法——竞争决策算法，利用竞争决策算法的通用模型，给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法，经过数据测试和验证，并与其它算法的结果进行了比较，得到了较好的结果．     

赋权有向图最小生成树的表上作业法

每一赋权有向图可用一个赋权表来表示。本文在借助于赋权表而不是赋权有向图本身讨论圈和生成树的基础上,给出了一种求解赋权有向图最小生成树的新方法——表上作业法,证明了方法的最优性。该方法简单易行,借助于计算机Ｓｐｒｅａｄｓｈｅｅｔ软件,如ＭｉｃｒｏｓｏｆｔＥｘｃｅｌ,可很方便地进行大规模复杂问题的求解。     

无人飞行器Ad hoc网络中基于容错的中继节点配置

针对无人飞行器Ad hoc网络的容错设计需求,采用增加中继节点的方法实现。在二维平面同构网络中,将容错问题转化为边长受限条件下最少数量Steiner点的Steiner树问题。提出了两种基于最小成本子图的中继节点配置算法,以求解最少数量的中继节点及其位置,使改变后的网络拓扑图为顶点2-连通,实现容错。第一种为多项式时间的8-近似算法;第二种为随机近似算法,采用文化基因算法,搜索需要新增加的最小成本强化边组合。仿真结果表明了所提算法的有效性,当网络规模较小和中等时,随机近似算法得到的中继节点数量较少,平均情况下性能较优。     

度限制最小树的蚂蚁算法①

针对度限制最小树问题,给出了一种基于蚂蚁系统思想的求解方法,经大量数据测试和验证,并与其它算法相比较,得到了较好的结果以及一系列有意义的结论.     

度限制最小树的蚂蚁算法

针对度限制最小树问题,给出了一种基于蚂蚁系统思想的求解方法,经大量数据测试和验证,并与其它算法相比较,得到了较好的结果以及一系列意义的结论。     

Reachability/controllability of high order mix-valued logical networks

This paper addresses the reachability/controllability of high order mix-valued logical control networks by using the semi-tensor product method, and presents some necessary and sufficient conditions for the reachability/controllability. The high order mix-valued logical network is converted into an algebraic form first, based on which the reachability/controllability of the system is then investigated, and several necessary and sufficient conditions are established. The study of several illustrative examples shows that our new method is very effective in dealing with the reachability/controllability of high order mix-valued logical control networks.     

严格第k最小支撑树问题

提出了严格第 k最小树的概念 .利用定长支撑树问题的复杂性 ,证明了求支撑树的长度分布L( G)问题是 NP-C的 ,从而证明了严格第 k最小支撑树问题也是 NP-C的 .对于 k=2的情况 ,给出了一个多项式时间算法 ,其时间复杂性为 $O( | EX| n^2 )$ ,其中 EX是正交换的集合 ,n是顶点数.     

(0,1)-MATRICES AND GENERALIZED ULTRAMETRIC MATRICES

1.IntroductionOvertheyears,becauseofthefrequentapplicationsofM-matricesineconomicmodels,neuralnetworksandlargescalesystems,M-matriceshavehadconsiderableattention(see[1,2]).Ann-by-nrealmatrixA=(ail)iscalledanM-matrixif1)itisoftheformA=al--PwherePisentrywisenonnegative,and2)aexceedsthespectralradiusofP.Recently,duetotheapplicationsofinverseM-matricesininversephysicalproblemsandintheregularizationofill-posedproblems(see[3,4]),anoticeableamountofattentionhasturnedtothestudyofinverseM-matrices-…     

Optimal Approach to SAR Image Despeckling

1 .ＩＮＴＲＯＤＵＣＴＩＯＮＩｔｈａｓｂｅｅｎｆｏｕｎｄｔｈａｔａｌｍｏｓｔａｌｌｍｏｄｅｒｎｒａｄａｒｉｍａｇｅｓａｒｅｓｔａｔｉｓｔｉｃａｌｌｙｉｎｈｏｍｏｇｅｎｅｏｕｓ,ｗｈｉｃｈｒｅｓｕｌｔｓｆｒｏｍｔｈｅｈｉｇｈｓｐａｔｉａｌｒｅｓｏｌｕｔｉｏｎｉｎｍｏｄｅｒｎｒａｄａｒｓ.Ａｓａｈｉｇｈ ｒｅｓｏｌｕｔｉｏｎａｃｔｉｖｅｍｉｃｒｏｗａｖｅｓｅｎｓｏｒ,ＳＡＲ ,ｗｉｔｈｉｔｓａｂｉｌｉｔｙｔｏｉｍａｇｅｔｈｅＥａｒｔｈ’ｓｓｕｒｆａｃｅｉｎｎｅａｒｌｙａｌｌｗｅａｔｈｅｒｃｏｎｄｉｔｉｏｎ…     

基于MST的拓扑感知度约束覆盖网构建算法

覆盖网能有效分离网络应用与底层网络基础设施,提升服务质量(quality of service, QoS)和用户体验(quality of users’ experience, QoE)。设计了一种普适性较强的覆盖网拓扑构建算法--基于最小生成树（minimum spanning tree, MST）的拓扑感知度约束(minimum spanning-tree based topology-aware degree bound, MST-TADB）覆盖网构建算法。该方法感知网络拓扑,逐步生成MST,同时参考节点的转发和计算能力作为节点度约束收敛算法。由仿真结果可知,和同类算法相比,本文方法的故障恢复率、恢复路径跳数惩罚、服务节点平均节点度和时间复杂度综合权衡较好,并保证了所构建的覆盖网的自愈性。     

最小硬件代价离散系数FIR滤波器的设计

针对高速并行脉动处理的需要 ,利用图的概念 ,给出了寻找利用最少硬件代价和最佳波动结构实现常系数乘法的系数表示算法 ,并用此法求得的离散系数设计FIR滤波器 ,提出了一种从连续系数到离散系数的优化算法。仿真结果表明 ,这种表示方法比传统的CSD码优越 ,而且离散系数滤波器的优化算法是有效的和必要的     

基于最小生成树与概率松弛结合的谱匹配算法

提出了一种基于最小生成树与概率松弛结合的谱匹配算法。该算法分别对给定的两个待匹配的特征点集构建最小生成树,通过最小生成树构造Laplace矩阵,由奇异值分解该矩阵得到的特征值和特征向量,计算出特征点匹配的初始概率,利用概率松弛迭代法,获得最终匹配结果。用大量的真实序列图像进行比较实验,结果验证了该算法的有效性和准确性。     

VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

OPTIMALITY CONDITIONS IN NONSMOOTH MULTIOBJECTIVE PROGRAMMING

ＯＰＴＩＭＡＬＩＴＹＣＯＮＤＩＴＩＯＮＳＩＮＮＯＮＳＭＯＯＴＨＭＵＬＴＩＯＢＪＥＣＴＩＶＥＰＲＯＧＲＡＭＭＩＮＧ￥ＷＡＮＧＬｉａｎｃｈｅｎｇ；ＤＯＮＧＪｉａｌｉ；ＬＩＵＱｉｎｇｈｕａｉ（ＤｅｐｅｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＪｉｌｉｎＵｎｉ...     

无线传感器网络中多移动代理分组优化算法

在基于多移动代理的无线传感器网络中,源节点的编组方法是区别于单移动代理系统的核心研究问题。基于跳数的最小生成树原理,提出一种基于最小生成树算法的规划编组方式,通过对无向全连通图中边权值的测量和选取,简单而有效地控制网络中能量消耗与任务延迟间的平衡,从而获得高效的综合性能。最后通过大量的OPNET仿真实验验证了算法的可靠性。

Abstract：

In contrary to the single mobile agent system,the grouping methodology for source nodes is the key issue in multi-agent itinerary planning for wireless sensor networks.A novel approach was proposed based on hop-oriented minimum spanning tree.The scheme achieves flexible trade-off control between energy cost and task duration by dynamically selecting edge weights in the total connected graph.Extensive simulations have shown that the approach outperforms the existing works.