{
  "id": "0910.3545",
  "version": "v1",
  "published": "2009-10-19T12:22:05.000Z",
  "updated": "2009-10-19T12:22:05.000Z",
  "title": "Random walks on networks: cumulative distribution of cover time",
  "authors": [
    "Nikola Zlatanov",
    "Ljupco Kocarev"
  ],
  "journal": "Phys. Rev. E 80, 041102 (2009)",
  "doi": "10.1103/PhysRevE.80.041102",
  "categories": [
    "math-ph",
    "math.MP"
  ],
  "abstract": "We derive an exact closed-form analytical expression for the distribution of the cover time for a random walk over an arbitrary graph. In special case, we derive simplified exact expressions for the distributions of cover time for a complete graph, a cycle graph, and a path graph. An accurate approximation for the cover time distribution, with computational complexity of O(2n), is also presented. The approximation is numerically tested only for graphs with n<=1000 nodes.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-10-19T12:22:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05.40.Fb",
      "02.50.Ga",
      "02.50.Cw"
    ],
    "keywords": [
      "random walk",
      "cumulative distribution",
      "cover time distribution",
      "exact closed-form analytical expression",
      "special case"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Physical Review E",
      "year": 2009,
      "month": "Oct",
      "volume": 80,
      "number": 4,
      "pages": "041102"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009PhRvE..80d1102Z"
    }
  }
}