𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maintaining Spanning Trees of Small Diameter

✍ Scribed by G. F. Italiano; R. Ramaswami

Publisher
Springer
Year
1998
Tongue
English
Weight
377 KB
Volume
22
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Minimum restricted diameter spanning tre
Minimum restricted diameter spanning trees
✍ Refael Hassin; Asaf Levin πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 304 KB

Let G = (V; E) be a requirement graph. Let d = (dij) n i; j=1 be a length metric. For a tree T denote by dT (i; j) the distance between i and j in T (the length according to d of the unique i -j path in T ). The restricted diameter of T , DT , is the maximum distance in T between pair of vertices wi

Diameter of random spanning trees in a g
Diameter of random spanning trees in a given graph
✍ Fan Chung; Paul Horn; L. Lu πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 144 KB πŸ‘ 1 views

## Abstract Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph __G__ is between and with high probability., w

A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
✍ Fred Buckley; Martin Lewinter πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 182 KB πŸ‘ 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th