On edge-disjoint spanning trees with small depths
Let G be a graph with n vertices. Suppose that there are k edge-disjoint spanning trees in G. We show that if the minimum degree of the vertices in G is at least kl, then there are k edge-disjoint spanning trees rooted at any vertex with depth O(n/l) in G. Also, we show that given a graph, a vertex r of the graph, and a positive integer k, the problem of finding k edge-disjoint spanning trees rooted at r with optimal depth is NP-hard. (C) 2000 Elsevier Science B.V. All rights reserved.
edge-disjoint spanning trees parallel processing broadcasting computational complexity np-hard