DOI: 10.1103/physrevlett.84.6118. Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs

Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs

10.1103/physrevlett.84.6118

Crossref journal-article

American Physical Society (APS)

Physical Review Letters (16)

Bibliography

Weigt, M., & Hartmann, A. K. (2000). Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs. Physical Review Letters, 84(26), 6118â6121.

Authors 2

Martin Weigt (first)
Alexander K. Hartmann (additional)

References 14 Referenced 112

{'volume-title': 'Computers and Intractability', 'year': '1979', 'author': 'M. R. Garey', 'key': 'PhysRevLett.84.6118Cc1R1'} / Computers and Intractability by M. R. Garey (1979)
{'volume-title': 'Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92)', 'year': '1992', 'author': 'D. Mitchell', 'key': 'PhysRevLett.84.6118Cc3R1'} / Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92) by D. Mitchell (1992)
10.1103/PhysRevE.56.1357 / Phys. Rev. E by R. Monasson (1997)
10.1038/22055 / Nature (London) by R. Monasson (1999)
10.1007/s100510051065 / Eur. Phys. J. B by G. Biroli (2000)
{'key': 'PhysRevLett.84.6118Cc8R1', 'first-page': '17', 'volume': '5', 'author': 'P. Erdös', 'year': '1960', 'journal-title': 'Publ. Math. Inst. Hung. Acad. Sci.'} / Publ. Math. Inst. Hung. Acad. Sci. by P. Erdös (1960)
{'volume-title': 'Random Graphs', 'year': '1985', 'author': 'B. Bollobas', 'key': 'PhysRevLett.84.6118Cc9R1'} / Random Graphs by B. Bollobas (1985)
10.1002/net.3230140302 / Network by P. G. Gazmuri (1984)
10.1016/S0012-365X(98)00048-X / Discr. Math. by J. Harant (1998)
10.1016/0012-365X(90)90149-C / Discr. Math. by A. M. Frieze (1990)
10.1287/opre.14.4.699 / Oper. Res. by E. L. Lawler (1966)
10.1137/0206038 / SIAM J. Comput. by R. E. Tarjan (1977)
10.1088/0305-4470/31/2/012 / J. Phys. A by R. Monasson (1998)
10.1103/PhysRevLett.58.164 / Phys. Rev. Lett. by I. Kanter (1987)

Dates

Type	When
Created	23 years ago (July 26, 2002, 10:19 p.m.)
Deposited	7 months, 2 weeks ago (Jan. 2, 2025, 6:33 p.m.)
Indexed	2 weeks, 2 days ago (Aug. 6, 2025, 9:04 a.m.)
Issued	25 years, 1 month ago (June 26, 2000)
Published	25 years, 1 month ago (June 26, 2000)
Published Online	25 years, 1 month ago (June 26, 2000)

Funders 0

None

BibTeX

@article{Weigt_2000, title={Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs}, volume={84}, ISSN={1079-7114}, url={http://dx.doi.org/10.1103/physrevlett.84.6118}, DOI={10.1103/physrevlett.84.6118}, number={26}, journal={Physical Review Letters}, publisher={American Physical Society (APS)}, author={Weigt, Martin and Hartmann, Alexander K.}, year={2000}, month=jun, pages={6118–6121} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        6
      ]
    ],
    "date-time": "2025-08-06T13:04:02Z",
    "timestamp": 1754485442352,
    "version": "3.32.0"
  },
  "reference-count": 14,
  "publisher": "American Physical Society (APS)",
  "issue": "26",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2000,
            6,
            26
          ]
        ],
        "date-time": "2000-06-26T00:00:00Z",
        "timestamp": 961977600000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "http://link.aps.org/licenses/aps-default-license"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "DOI": "10.1103/physrevlett.84.6118",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T02:19:13Z",
    "timestamp": 1027736353000
  },
  "page": "6118-6121",
  "source": "Crossref",
  "is-referenced-by-count": 112,
  "title": "Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs",
  "prefix": "10.1103",
  "volume": "84",
  "author": [
    {
      "given": "Martin",
      "family": "Weigt",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Alexander K.",
      "family": "Hartmann",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "16",
  "published-online": {
    "date-parts": [
      [
        2000,
        6,
        26
      ]
    ]
  },
  "reference": [
    {
      "volume-title": "Computers and Intractability",
      "year": "1979",
      "author": "M. R. Garey",
      "key": "PhysRevLett.84.6118Cc1R1"
    },
    {
      "volume-title": "Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92)",
      "year": "1992",
      "author": "D. Mitchell",
      "key": "PhysRevLett.84.6118Cc3R1"
    },
    {
      "key": "PhysRevLett.84.6118Cc4R1",
      "doi-asserted-by": "crossref",
      "first-page": "1357",
      "DOI": "10.1103/PhysRevE.56.1357",
      "volume": "56",
      "author": "R. Monasson",
      "year": "1997",
      "journal-title": "Phys. Rev. E"
    },
    {
      "key": "PhysRevLett.84.6118Cc5R1",
      "doi-asserted-by": "crossref",
      "first-page": "133",
      "DOI": "10.1038/22055",
      "volume": "400",
      "author": "R. Monasson",
      "year": "1999",
      "journal-title": "Nature (London)"
    },
    {
      "key": "PhysRevLett.84.6118Cc7R1",
      "doi-asserted-by": "crossref",
      "first-page": "551",
      "DOI": "10.1007/s100510051065",
      "volume": "14",
      "author": "G. Biroli",
      "year": "2000",
      "journal-title": "Eur. Phys. J. B"
    },
    {
      "key": "PhysRevLett.84.6118Cc8R1",
      "first-page": "17",
      "volume": "5",
      "author": "P. Erd\u00f6s",
      "year": "1960",
      "journal-title": "Publ. Math. Inst. Hung. Acad. Sci."
    },
    {
      "volume-title": "Random Graphs",
      "year": "1985",
      "author": "B. Bollobas",
      "key": "PhysRevLett.84.6118Cc9R1"
    },
    {
      "key": "PhysRevLett.84.6118Cc10R1",
      "doi-asserted-by": "crossref",
      "first-page": "367",
      "DOI": "10.1002/net.3230140302",
      "volume": "14",
      "author": "P. G. Gazmuri",
      "year": "1984",
      "journal-title": "Network"
    },
    {
      "key": "PhysRevLett.84.6118Cc11R1",
      "doi-asserted-by": "crossref",
      "first-page": "239",
      "DOI": "10.1016/S0012-365X(98)00048-X",
      "volume": "188",
      "author": "J. Harant",
      "year": "1998",
      "journal-title": "Discr. Math."
    },
    {
      "key": "PhysRevLett.84.6118Cc12R1",
      "doi-asserted-by": "crossref",
      "first-page": "171",
      "DOI": "10.1016/0012-365X(90)90149-C",
      "volume": "81",
      "author": "A. M. Frieze",
      "year": "1990",
      "journal-title": "Discr. Math."
    },
    {
      "key": "PhysRevLett.84.6118Cc13R1",
      "doi-asserted-by": "crossref",
      "first-page": "699",
      "DOI": "10.1287/opre.14.4.699",
      "volume": "14",
      "author": "E. L. Lawler",
      "year": "1966",
      "journal-title": "Oper. Res."
    },
    {
      "key": "PhysRevLett.84.6118Cc14R1",
      "doi-asserted-by": "crossref",
      "first-page": "537",
      "DOI": "10.1137/0206038",
      "volume": "6",
      "author": "R. E. Tarjan",
      "year": "1977",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "PhysRevLett.84.6118Cc16R1",
      "doi-asserted-by": "crossref",
      "first-page": "513",
      "DOI": "10.1088/0305-4470/31/2/012",
      "volume": "31",
      "author": "R. Monasson",
      "year": "1998",
      "journal-title": "J. Phys. A"
    },
    {
      "key": "PhysRevLett.84.6118Cc19R1",
      "doi-asserted-by": "crossref",
      "first-page": "164",
      "DOI": "10.1103/PhysRevLett.58.164",
      "volume": "58",
      "author": "I. Kanter",
      "year": "1987",
      "journal-title": "Phys. Rev. Lett."
    }
  ],
  "container-title": "Physical Review Letters",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://link.aps.org/article/10.1103/PhysRevLett.84.6118",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "syndication"
    },
    {
      "URL": "http://harvest.aps.org/v2/journals/articles/10.1103/PhysRevLett.84.6118/fulltext",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        1,
        2
      ]
    ],
    "date-time": "2025-01-02T23:33:17Z",
    "timestamp": 1735860797000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://link.aps.org/doi/10.1103/PhysRevLett.84.6118"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2000,
        6,
        26
      ]
    ]
  },
  "references-count": 14,
  "journal-issue": {
    "issue": "26",
    "published-print": {
      "date-parts": [
        [
          2000,
          6
        ]
      ]
    }
  },
  "URL": "http://dx.doi.org/10.1103/PhysRevLett.84.6118",
  "relation": {},
  "ISSN": [
    "0031-9007",
    "1079-7114"
  ],
  "subject": [],
  "container-title-short": "Phys. Rev. Lett.",
  "published": {
    "date-parts": [
      [
        2000,
        6,
        26
      ]
    ]
  }
}