Distributed Construction of Almost-Edge-Disjoint Spanning Trees via

A $k$-dense tree, $k$ integer $\geq 1$, is a natural extension of a tree. A leaf is a vertex connected to the rest of the structure through $\leq k$ edges. After the removal of a leaf, the structure still has other leaves. Among other applications, dense trees can be used as interconnection structures in a network. Representing the network in connected graph form $G=(V,E)$, we construct a $k$-dense tree $T$ as a subgraph of $G$ spanning all its vertices. $T$ is then decomposed in $k$ {\em super-root spanning trees} sharing a $k$-clique $C$ of vertices. These trees are edge-disjoint except for the common edges in $C$. Each vertex is labeled with a set of $k$ integers in $\{0,1,\ldots,n-1\}$, $n=|V|$, to set up an interval routing scheme for $G$ along the edges of $T$. The constructions are implemented as distributed algorithms all requiring polynomial time