Spanning tree algorithms for connectivity and routing in communication networks

This dissertation discusses three spanning tree problems for connectivity and routing in communication networks. Let G = (V, E) be an undirected graph with n nodes in V and m edges in E, and let T be a minimum spanning tree (MST) of G. The node replacement R(v) for node v is the minimum weight set of edges that reconnect the components of {dollar}T - v.{dollar} We present two algorithms that find R(v) for all v, simultaneously. The sequential algorithm Find Node Replacements (FNR) takes {dollar}O(malpha(m,n)){dollar} time if the edges of E are presorted by weight, O(m log n) time if not, where {dollar}alpha(m, n){dollar} is the functional inverse of Ackermann's function. The algorithm Find Node Replacements in Parallel (FNRP) takes {dollar}O(logsp2 n){dollar} time using m processors on a CREW PRAM.; The edge replacement r(t) for edge t in E(T) is the minimum weight edge that reconnects the two components of {dollar}T - t.{dollar} We present two algorithms that find r(t) for all t, simultaneously. The sequential algorithm Find Edge Replacements (FER) takes O(m) time if the edges are presorted, O(m log n) time if not. The algorithm Find Edge Replacements in Parallel (FERP) takes O(log n) time using m processors on a CREW PRAM.; Both FNRP and FERP use a vector-valued rake-and-compress algorithm that needs only m processors on a CREW PRAM, instead of the {dollar}nsp2{dollar}/log n processors for the basic rake-and-compress algorithm of Miller and Reif.; Finally, we present a family of routing algorithms for ad hoc networks that use a spine infrastructure to coordinate routing and topology updates. The spine is an approximate minimum connected dominating set. The family of routing algorithms includes a basic algorithm, in which each spine node has a local copy of G; a hierarchical algorithm, which scales well with network size; and a partial-information algorithm, which explores the tradeoff of route optimality versus the amount of overhead. We present worst-case analyses and simulation results that show how well the spine routing algorithms maintain shortest-path or near-shortest-path routes with reasonable overhead, even when nodes move frequently.