The Longest Minimum-Weight Path in a Complete Graph

被引：11

作者：

Addario-Berry, Louigi ^{[1
]}

Broutin, Nicolas ^{[2
]}

Lugosi, Gabor ^{[3
]}

机构：

[1] Univ Montreal, Dept Math & Stat, Montreal, PQ H3C 3J7, Canada

[2] INRIA Rocquencourt, Projet Algorithms, F-78153 Le Chesnay, France

[3] Pompeu Fabra Univ, Dept Econ, Barcelona 08005, Spain

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2010年 / 19卷 / 01期

关键词：

SHORTEST-PATH; TREES; HEIGHTS;

D O I：

10.1017/S0963548309990204

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the minimum-weight path between any pair of nodes of the n-vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the longest of these minimum-weight paths has about alpha* log n edges, where alpha* approximate to 3.5911 is the unique solution of the equation alpha log alpha - alpha = 1. This answers a question posed by Janson [8].

引用

页码：1 / 19

页数：19

共 15 条

[1]

Alon N., 2015, PROBABILISTIC METHOD

[2]

[Anonymous], 1960, Mathematical Proceedings of the Cambridge Philosophical Society, DOI DOI 10.1017/S0305004100034241

[3]

Dembo A., 1998, Large Deviation Techniques and Applications

[4]

DEVROYE L, 1987, ACTA INFORM, V24, P277, DOI 10.1007/BF00265991

[5] CORRELATION INEQUALITIES ON SOME PARTIALLY ORDERED SETS [J].

FORTUIN, CM ;

KASTELEY.PW ;

GINIBRE, J .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1971, 22 (02) :89-&

[6]

GRIMMETT G, 1999, SERIES COMPREHENSIVE, V321

[7] The weight and hopcount of the shortest path in the complete graph with exponential weights [J].

Hooghiemstra, Gerard ;

Van Mieghem, Piet .

COMBINATORICS PROBABILITY & COMPUTING, 2008, 17 (04) :537-548

[8] One, two and three times log n/n for paths in a complete graph with random weights [J].

Janson, S .

COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (04) :347-361

[9] NOTE ON THE HEIGHTS OF RANDOM RECURSIVE TREES AND RANDOM M-ARY SEARCH-TREES [J].

PITTEL, B .

RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (02) :337-347

[10]

Robbins H., 1955, Amer. Math. Monthly, V62, P26, DOI [10.2307/2308012, DOI 10.2307/2308012]

← 1 2 →