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 条

[11]

Rogers L.C.G., 2000, Diffusions, Markov Processes and Martingales, V1

[12]

Shorack G. R., 1986, EMPIRICAL PROCESSES

[13]

Smythe R., 1995, THEORY PROBAB MATH S, V51, P1

[14] The weight of the shortest path tree [J].

van der Hofstad, Remco ;

Hooghiemstra, Gerard ;

Van Mieghem, Piet .

RANDOM STRUCTURES & ALGORITHMS, 2007, 30 (03) :359-379

[15] Size and weight of shortest path trees with exponential link weights [J].

Van Der Hofstad, Remco ;

Hooghiemstra, Gerard ;

Van Mieghem, Piet .

COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (06) :903-926

← 1 2 →