树形广播网络的最佳源点和最佳源点对

广播就是通信风格中的某些已知消息的成员（称为源点）将消息传递给其它所有成员的过程．通信网络一般用图来描述．从不同的网络成员广播一条消息所需的最少时间一般是不同的．本文在树网络中设计了选取一个或一对源点使广播时间最短的算法，这样的一个或一对源点称为最佳源点或最佳源点对．     

广播网络的最佳源点集

广播是研究通信网络的某个成员的消息如何尽快地传递给所有其它成员的消息传递问题,有两类常见的通信模式,一类是shouting模式,即在一个单位时间内,一个顶点能够和它的户斤有邻点通信;另一类是whispering模式,即在一个单位时间以内,一个顶点最多只能和它的一个邻点通信,通信网络通常用图来描述,最初贮存消息的网络成员称为源点。     

"等周等积定理"的两个推广

文 [1 ]证明了“对任一直角三角形 ,存在等周等积的矩形”.本文作如下推广 :定理 1　对任意直角三角形 ,总存在一个矩形 ,使得矩形与直角三角形的周长和面积比等于常数 k( k≥ 1 ) .证明　在 Rt△ ABC中 ,设直角边为 a、b,斜边为 c,我们要求长为 x,宽为 y的矩形 ,使得方程组2 ( x y) =k( a b c) ,xy =k .12 ab.有正解 ,仅需证明方程t2 - k( a b c)2 t 12 kab =0有正解 .事实上 ,由于 k≥ 1 ,c2 =a2 b2 ≥2 ab,c >a >0 ,c>b >0 ,从而Δ =[- k( a b c)2 ]2 - 4× 1× 12 kab≥ k2 ( a b c) 24 - 2 k2 ab=k24 ( a2 b2…     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

相依假设下样本相关矩阵最大元的渐近分布

设{Xk,i;k≥1,i≥1)是一随机变量组列,令{pn;n≥1)是一正整数序列,满足c1≤n/pn≤c2,其中c1,c2是正实数.假设{Xk,i;k≥1,i≥1}满足一些相依条件,得到了Ln的渐近分布,这里Ln= ,以及表示(X1,i,…,Xn,i)'和(X1,j,…,Xn,j)'间的Pearson相关系数.     

一类无向Kautz图的k限制边连通度的上界

在Moor-Shannon网络模型中,k限制边连通度较大的网络一般有较好的可靠性和容错性.本文在无向Kautz图UK(2,n)中研究k限制边连通度的上界ξk,证明了ξ5(UK(2,3))=6,ξ5(UK(2,n))=8,n≥4,且当4≤k≤n时,ξk(UK(2,n))≤2(k-「k/3」).     

一类条件最小值问题的统一解法

本文给出一类条件最小值问题及其统一的解法,这类问题是:已知a,b,c为正实数,且a+b+c=1,k(k≠0,1)为整数,求(a+b)k+(b+c)k+(c+a)k的最小值.统一解法使用的工具是n(n≥2)元均值不等式:a1+a2+…+an≥nna1a2…槡an(ai>0,i=     

一个分式不等式猜想的证明

《数学通报》2010年第12期的文[1]中提出了如下猜想:对于a,b,c∈R+,k∈N,k≥2,不等式ak/ak-1b+…bk+bk/bk+bk-1c+…ck+ck/ck+ck-1a+…ak≥3/k+a (1)本文将证明猜想式(1)是正确的.为证(1)式正确,先给出两个引理.     

相依回归系统回归系数的待定系数估计

对于两个相依线性回归方程组成的系统(1．1)，本文提出了β1的待定系数估计β^*1（k，c)=（x′1x1 k1)^-1(x′1y1-cσ12/σ22x′1N2y2)，其中岭参数k≥0．c是待定系数．与β^*1(k，c)对应的非限定两步估计记为β^41(T，k，c)．当c=1时β^*1(k,1)=β1(k)和β^*1(T,k,1)=β1(T,k)等干[6]引入的一双有偏估计，结果表明总可以选取适当的c值和k值使β^*1(k，c)和β^*1(T,k，c)在均方误差阵准则下分别优于β1和β1(T)，并讨论了c值的最佳选择问题．     

等周等积定理的两个再推广

文 [1 ]证明了“对任意直角三角形总存在一个矩形 ,使得矩形与三角形的周长和面积比均等于常数 k( k≥ 1 )”.本文作如下推广 :定理 1　对任意梯形 ,总存在一个矩形 ,使得矩形与这梯形的周长和面积比均等于常数 k( k≥ 1 ) .证明　在梯形 ABCD中 ,设 AD∥ BC,且 AD =a,BC=b,两腰 AB=c,CD =d,要求长为 x,宽为 y的矩形 ,使得方程组2 ( x + y) =k( a + b + c + d) ,xy =k .12 ( a + b) dsin C.有正解 ,仅需证明方程t2 - k( a + b + c + d)2 t+ 12 k( a + b) dsin C= 0有正解 .事实上 ,由于 k≥ 1 ,　 0 相似文献   

Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.     

Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.     

Rumor spreading on random regular graphs and expanders

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well‐studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d ‐regular graphs with n vertices. We show that with probability 1 ‐ o(1) the push model broadcasts the message to all nodes within (1 + o(1))C_d lnn rounds, where Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo‐random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + o(1))Clnn with probability 1 ‐ o(1), where \begin{align*}C = \lim_{d\to\infty}C_d = \frac{1}{\ln2} + 1\end{align*}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

A decomposition approach for solving a broadcast domination network design problem

We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f _i assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f _k -value whose shortest distance to node j is no more than f _k . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation.     

On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption

This paper provides an exposition of methods by which a trusted authority can distribute keys and/or broadcast a message over a network, so that each member of a privileged subset of users can compute a specified key or decrypt the broadcast message. Moreover, this is done in such a way that no coalition is able to recover any information on a key or broadcast message they are not supposed to know. The problems are studied using the tools of information theory, so the security provided is unconditional (i.e., not based on any computational assumption).We begin by surveying some useful schemes for key distribution that have been presented in the literature, giving background and examples (but not too many proofs). In particular, we look more closely at the attractive concept of key distribution patterns, and present a new method for making these schemes more efficient through the use of resilient functions. Then we present a general approach to the construction of broadcast schemes that combines key predistribution schemes with secret sharing schemes. We discuss the Fiat-Naor Broadcast Scheme, as well as other, new schemes that can be constructed using this approach.     

Some New Results on Key Distribution Patterns and Broadcast Encryption

This paper concerns methods by which a trusted authority can distribute keys and/or broadcast a message over a network, so that each member of a privileged subset of users can compute a specified key or decrypt the broadcast message. Moreover, this is done in such a way that no coalition is able to recover any information on a key or broadcast message they are not supposed to know. The problems are studied using the tools of information theory, so the security provided is unconditional (i.e., not based on any computational assumption).In a recent paper st95a, Stinson described a method of constructing key predistribution schemes by combining Mitchell-Piper key distribution patterns with resilient functions; and also presented a construction method for broadcast encryption schemes that combines Fiat-Naor key predistribution schemes with ideal secret sharing schemes. In this paper, we further pursue these two themes, providing several nice applications of these techniques by using combinatorial structures such as orthogonal arrays, perpendicular arrays, Steiner systems and universal hash families.     

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures

Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability; faults are permanent and Byzantine, while all nodes are fault-free. In a unit of time, each node can communicate with at most one other node. We present a broadcasting algorithm which works fornnodes in timeO(log n) with probability of correctness exceeding 1 − 1/n, for sufficiently largen.