{
  "id": "0807.3373",
  "version": "v1",
  "published": "2008-07-21T23:32:06.000Z",
  "updated": "2008-07-21T23:32:06.000Z",
  "title": "Statistical Mechanics of Steiner trees",
  "authors": [
    "M. Bayati",
    "C. Borgs",
    "A. Braunstein",
    "J. Chayes",
    "A. Ramezanpour",
    "R. Zecchina"
  ],
  "journal": "Phys. Rev. Lett. 101, 037208 (2008)",
  "doi": "10.1103/PhysRevLett.101.037208",
  "categories": [
    "cond-mat.stat-mech",
    "cond-mat.dis-nn"
  ],
  "abstract": "The Minimum Weight Steiner Tree (MST) is an important combinatorial optimization problem over networks that has applications in a wide range of fields. Here we discuss a general technique to translate the imposed global connectivity constrain into many local ones that can be analyzed with cavity equation techniques. This approach leads to a new optimization algorithm for MST and allows to analyze the statistical mechanics properties of MST on random graphs of various types.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-07-21T23:32:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "64.60.aq",
      "05.20.-y",
      "87.18.Vf",
      "89.70.Eg"
    ],
    "keywords": [
      "statistical mechanics",
      "minimum weight steiner tree",
      "important combinatorial optimization problem",
      "imposed global connectivity constrain",
      "cavity equation techniques"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Physical Review Letters",
      "year": 2008,
      "month": "Jul",
      "volume": 101,
      "number": 3,
      "pages": "037208"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008PhRvL.101c7208B"
    }
  }
}