Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0020-0190(00)00078-8 | Inf. Process. Lett. |
Keywords | Field | DocType |
small depth,parallel processing,np hard,spanning tree,computational complexity,broadcasting | Wheel graph,Discrete mathematics,Combinatorics,Trémaux tree,Graph power,Bound graph,Graph factorization,Cycle graph,Neighbourhood (graph theory),Spanning tree,Mathematics | Journal |
Volume | Issue | ISSN |
75 | 1-2 | 0020-0190 |
Citations | PageRank | References |
5 | 0.46 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toru Hasunuma | 1 | 142 | 16.00 |