Steiner trees in the stochastic mean-field model of distance
52 mins 19 secs,
95.71 MB,
MP3
44100 Hz,
249.78 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Ayalvadi Ganesh
Thursday 3rd November 2016 - 14:00 to 15:00 |
|---|
| Created: | 2016-11-11 15:50 |
|---|---|
| Collection: | Theoretical Foundations for Statistical Network Analysis |
| Publisher: | Isaac Newton Institute |
| Copyright: | Ayalvadi Ganesh |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| Abstract: | Consider the complete graph on n nodes with iid exponential weights of unit mean on the edges. A number of properties of this model have been investigated including first passage percolation, diameter, minimum spanning tree, etc. In particular, Janson showed that the typical distance between two nodes scales as (log n)/n, whereas the diameter (maximum distance between any two nodes) scales as 3(log n)/n. Bollobas et al. showed that, for any fixed k, the weight of the Steiner tree connecting k typical nodes scales as (k-1)log n/n, which recovers Janson's result for k=2. We extend this result to show that the worst case k-Steiner tree, over all choices of k nodes, has weight scaling as (2k-1)log n/n. Further, Janson derived the limiting distribution of the typical distance between two nodes. We refine the result of Bollobas et al. and present a perhaps surprising result in this direction for the typical Steiner tree which has implications for the limiting shape of the 3-Steiner tree. This is joint work with Angus Davidson and Balint Toth. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.91 Mbits/sec | 749.02 MB | View | Download | |
| WebM | 640x360 | 737.22 kbits/sec | 282.31 MB | View | Download | |
| iPod Video | 480x270 | 489.94 kbits/sec | 187.56 MB | View | Download | |
| MP3 * | 44100 Hz | 249.78 kbits/sec | 95.71 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||