We present a fast construction algorithm for the hierarchical tree decompositions that lie at the heart of oblivious routing strategies and that form the basis for approximation and online algorithms for various cut problems in graphs. Given an undirected graph G = (V, E, c) with edge capacities, we compute a single tree T = (VT,ET,cT), where the leaf nodes of T correspond to nodes in G, such that the tree approximates the cut-structure of G up to a factor of (log4 n). The best existing construction by Harrelson, Hildrum, and Rao [12] just guarantees a polynomial running time but offers a better approximation guarantee of (log2 n log log n). Phrasing our results in terms of vertex sparsifiers, we obtain the following: For a graph G = (V, E) with a subset S of terminals, we compute a tree T with at most 2|S| vertices (and the leafs of T correspond to nodes in S) such that T is a flow-sparsifier for S in G with quality (log2 nlog2 k), where |V| = n and |S| = k. The running time is (polylogn · T(m, 1/log3n)) where T(m, ∊) is the time for computing an approximate maxflow in a graph with m edges. The latter is almost linear due to the recent results of Sherman [23] and Kelner et al. [13].

Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This article shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (slightly extended) skip graph, SKIP + , in polylogarithmic time from any given initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, our algorithm handles individual joins and leaves locally and efficiently.

Peer-to-peer systems rely on scalable overlay networks that enable efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This paper shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (variant of the) skip graph in polylogarithmic time from any initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, individual joins and leaves are handled locally and require little work.