{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:03Z","timestamp":1787323383184,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS1362785"],"award-info":[{"award-number":["DMS1362785"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF1522984"],"award-info":[{"award-number":["CCF1522984"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS1363136"],"award-info":[{"award-number":["DMS1363136"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["333329"],"award-info":[{"award-number":["333329"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We determine, asymptotically in $n$, the distribution and mean of the weight of a minimum-weight $k$-clique (or any strictly balanced graph $H$) in a complete graph $K_n$ whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (nonasymptotic) bounds on the distribution's cumulative distribution function in a form obtained directly from the Stein--Chen method and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of $k$ and $n$. The results may be applied to evaluate whether an observed minimum-weight copy of a graph $H$ in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure.<\/jats:p>","DOI":"10.1137\/17m1138303","type":"journal-article","created":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T10:57:06Z","timestamp":1534244226000},"page":"2115-2133","source":"Crossref","is-referenced-by-count":1,"title":["The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights"],"prefix":"10.1137","volume":"32","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wesley","family":"Pegden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4935-7820","authenticated-orcid":true,"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991491"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100058655"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"I. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo,\n                      The maximum clique problem\n                      , in Handbook of Combinatorial Optimization, D.Z. Du and P. M. Pardalos, eds., Kluwer Academic Publishers, Norwell, MA, 1999.","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"atypb4","unstructured":"S. Cai and J. Lin,\n                      Fast solving maximum weight clique problem in massive graphs\n                      , in Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016, PP. 568-574."},{"key":"atypb5","unstructured":"Clique problem\n                      , Wikipedia, revised 20 May 2017, 08:40 UTC."},{"key":"atypb6","unstructured":"Erlang distribution\n                      , Wikipedia, revised 2 June 2017, 20:04 UTC."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.2307\/2331961"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/19.3-4.225"},{"key":"atypb9","unstructured":"N. L. Johnson, S. Kotz, and N. Balakrishnan, eds.\n                      Continuous Univariate Distributions\n                      , 2nd ed., Vol. 1, Wiley, New York, 1995."},{"key":"atypb10","unstructured":"N. L. Johnson, S. Kotz, and N. Balakrishnan, eds.\n                      Continuous Univariate Distributions\n                      , 2nd ed., Vol. 2, Wiley, New York, 1995."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0003111"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1138303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:17Z","timestamp":1787320757000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1138303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1138303"],"URL":"https:\/\/doi.org\/10.1137\/17m1138303","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}