Search

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]