On the value of a random minimum spanning tree problem (Q1066149): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: DBLP publication ID (P1635): journals/dam/Frieze85, #quickstatements; #temporary_batch_1731543907597 |
||
| (5 intermediate revisions by 4 users not shown) | |||
| Property / author | |||
| Property / author: Alan M. Frieze / rank | |||
| Property / author | |||
| Property / author: Alan M. Frieze / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / Wikidata QID | |||
| Property / Wikidata QID: Q56484417 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3286850 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the connectivity of random m-orientable graphs and digraphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the shortest spanning subtree of a graph and the traveling salesman problem / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Optimization Problems on Graphs with Independent Random Edge Weights / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the Expected Value of a Random Assignment Problem / rank | |||
Normal rank | |||
| Property / DBLP publication ID | |||
| Property / DBLP publication ID: journals/dam/Frieze85 / rank | |||
Normal rank | |||
Latest revision as of 01:32, 14 November 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the value of a random minimum spanning tree problem |
scientific article |
Statements
On the value of a random minimum spanning tree problem (English)
0 references
1985
0 references
The lengths of the edges in a complete graph of order n are independent identically distributed random variables. Under mild conditions the length of the minimum spanning tree is shown to converge in probability as \(n\to \infty\), and the limiting value of the expected length is determined.
0 references
edge length
0 references
complete graph
0 references
minimum spanning tree
0 references
