Search

Abstract: Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of in polynomial time with respect to and the maximum degree Δ of G. We present two approaches. The first algorithm for this problem runs in time for every graph G with vertex expansion at least . The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l, leads to running time. We also present an extension of this method to test the biconnectivity of in time. [Copyright &y& Elsevier]

We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random r-regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728-740], where it was shown with high probability (whp) that for r ≥ 3 the cover time is asymptotic to θrn ln n, where θr = (r-1)/(r-2). In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph G. For k independent walks on G, the cover time CG(k) is asymptotic to CG/k, where CG is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is θrn/(2k). If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to 2lnk/k θrn as k, n→∞. We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to (2ln2)θrn as k→∞. The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to 2θrn. Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with k predators and ℓ prey the expected detection time is θrHℓn/k, where Hℓ is the ℓth harmonic number. [ABSTRACT FROM AUTHOR]

We consider the maximum generalised network flow problem and a supply-scaling algorithmic framework for this problem. We present three network-modification operations, which may significantly decrease the size of the network when the remaining node supplies become small. We use these three operations in Goldfarb et al.'s supply-scaling algorithm and prove an O˜(m2n log B) bound on the running time of the resulting algorithm. The previous best time bounds on computing maximum generalised flows are the O(m1.5n2 log B) bound of Kapoor and Vaidya's algorithm based on the interior-point method, and the O˜(m3 log B) bound of Goldfarb et al.'s algorithm. [Copyright &y& Elsevier]

Abstract: We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself. One model we consider is a network constructed in this fashion, in which vertices join but never leave. If is the size of the network, then the diameter of the network is for all , with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least . With high probability the network reconnects itself by replacing lost edges using tokens from the token pool. [Copyright &y& Elsevier]