首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 93 毫秒
1.
This paper addresses the flooding problem in dynamic graphs, where flooding is the basic mechanism in which every node becoming aware of a piece of information at step tt forwards this information to all its neighbors at all forthcoming steps t>tt>t. We show that a technique developed in a previous paper, for analyzing flooding in a Markovian sequence of Erdös–Rényi graphs, is robust enough to be used also in different contexts. We establish this fact by analyzing flooding in a sequence of graphs drawn independently at random according to a model of random graphs with given expected degree sequence. In the prominent case of power-law degree distributions, we prove that flooding takes almost surely O(logn)O(logn) steps even if, almost surely, none of the graphs in the sequence is connected. In the general case of graphs with an arbitrary degree sequence, we prove several upper bounds on the flooding time, which depend on specific properties of the degree sequence.  相似文献   

2.
Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any Dn/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996  相似文献   

3.
The communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. In the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. The spectral lower bound of λ2|V|/4 for the bisection width of a graph is widely known. The bisection width is equal to λ2|V|/4 iff all vertices are incident to λ2/2 cut edges in every optimal bisection.

We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion properties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on λ2β|V| with . We also present examples of graphs for which our new bounds are tight up to a constant factor. As a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular Ramanujan graphs.  相似文献   


4.
It has been recently proposed that natural connectivity can be used to efficiently characterise the robustness of complex networks. The natural connectivity quantifies the redundancy of alternative routes in the network by evaluating the weighted number of closed walks of all lengths and can be seen as an average eigenvalue obtained from the graph spectrum. In this article, we explore both analytically and numerically the natural connectivity of regular ring lattices and regular random graphs obtained through degree-preserving random rewirings from regular ring lattices. We reformulate the natural connectivity of regular ring lattices in terms of generalised Bessel functions and show that the natural connectivity of regular ring lattices is independent of network size and increases with K monotonically. We also show that random regular graphs have lower natural connectivity, and are thus less robust, than regular ring lattices.  相似文献   

5.
In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle.  相似文献   

6.
Impossibility results and best-case lower bounds are proved for the number of message delays and the number of processes required to reach agreement in an asynchronous consensus algorithm that tolerates non-Byzantine failures. General algorithms exist that achieve these lower bounds in the normal case, when the response time of non-faulty processes and the transmission delay of messages they send to one another are bounded. Our theorems allow algorithms to do better in certain exceptional cases, and such algorithms are presented. Two of these exceptional algorithms may be of practical interest.  相似文献   

7.
In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the bisection width of random dd-regular graphs, for any value of dd. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of dd-regular graphs. We provide bounds for 5≤d≤125d12. We also give empirical values of the size of the bisection found by the algorithm for some small values of dd and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum bisection.  相似文献   

8.
We present algorithmic lower bounds on the size sdsd of the largest independent sets of vertices in random dd-regular graphs, for each fixed d≥3d3. For instance, for d=3d=3 we prove that, for graphs on nn vertices, sd≥0.43475nsd0.43475n with probability approaching one as nn tends to infinity.  相似文献   

9.
Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no “nice” characterization of mortal graphs exists).  相似文献   

10.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号