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.