{
  "id": "1112.6330",
  "version": "v2",
  "published": "2011-12-29T15:31:08.000Z",
  "updated": "2015-04-16T13:15:29.000Z",
  "title": "The diameter of weighted random graphs",
  "authors": [
    "Hamed Amini",
    "Marc Lelarge"
  ],
  "comment": "Published at http://dx.doi.org/10.1214/14-AAP1034 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2015, Vol. 25, No. 3, 1686-1727",
  "doi": "10.1214/14-AAP1034",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In this paper we study the impact of random exponential edge weights on the distances in a random graph and, in particular, on its diameter. Our main result consists of a precise asymptotic expression for the maximal weight of the shortest weight paths between all vertices (the weighted diameter) of sparse random graphs, when the edge weights are i.i.d. exponential random variables.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-29T15:31:08.000Z",
      "title": "The Diameter of Weighted Random Graphs",
      "abstract": "In this paper we study the impact of the introduction of edge weights on the typical distances in a random graph and, in particular, on its diameter. Our main result consists of a precise asymptotic expression for the maximal weight of the shortest weight path between a random vertex and all others (the flooding time), as well as the (weighted) diameter of sparse random graphs, when the edge weights are i.i.d. exponential random variables.",
      "comment": "47 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-04-16T13:15:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80",
      "90B15"
    ],
    "keywords": [
      "weighted random graphs",
      "edge weights",
      "precise asymptotic expression",
      "main result consists",
      "shortest weight path"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 47,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.6330A"
    }
  }
}