{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:10Z","timestamp":1787323150514,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS1952285"],"award-info":[{"award-number":["DMS1952285"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We consider the following question. We have a dense regular graph $G$ with degree $\\alpha n$, where $\\alpha&gt;0$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $X(e),e\\in E(G(m))$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph but scaled by a factor $\\alpha^{-1}$. We consider spanning trees, shortest paths, and perfect matchings in (pseudorandom) bipartite graphs.<\/jats:p>","DOI":"10.1137\/20m1335418","type":"journal-article","created":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T15:28:44Z","timestamp":1623166124000},"page":"1182-1200","source":"Crossref","is-referenced-by-count":3,"title":["The Effect of Adding Randomly Weighted Edges"],"prefix":"10.1137","volume":"35","author":[{"given":"Alan M.","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"E. Aigner-Horev and D. Hefetz,\n                      Rainbow Hamilton Cycles in Randomly Coloured Randomly Perturbed Dense Graphs\n                      ,https:\/\/arxiv.org\/pdf\/2004.08637.pdf, 2020.","DOI":"10.1007\/978-3-030-83823-2_25"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192719"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1015"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22461"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000366"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009825"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP753"},{"key":"atypb8","first-page":"1907","volume":"20","author":"Bhamidi S.","year":"2010","journal-title":"Ann. Probab."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20885"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10070"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10112"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2017.06.033"},{"key":"atypb13","first-page":"390","volume":"2018","author":"Dadush D.","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548320000231"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20870"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/15M1047672"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. M. Frieze and M. Karo\u0144ski,\n                      Introduction to Random Graphs\n                      , Cambridge University Press, Cambridge, 2015.","DOI":"10.1017\/CBO9781316339831"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.37236\/1519"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.12.005"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010209"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003892"},{"key":"atypb24","first-page":"1","author":"Karp R. M.","year":"1987","journal-title":"New York"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000079"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032910"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20097"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-003-0308-9"},{"key":"atypb29","first-page":"25","author":"McDowell A.","year":"2018","journal-title":"Electron. J. Combin."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20084"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103118"},{"key":"atypb32","unstructured":"G. Parisi,\n                      A Conjecture on Random Bipartite Matching\n                      , Physics e-Print archive, 1998."},{"key":"atypb33","unstructured":"E. Powierski,\n                      Ramsey Properties of Randomly Perturbed Dense Graphs\n                      ,https:\/\/arxiv.org\/pdf\/1902.02197.pdf, 2019."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.25155"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90101-5"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/070683386"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/0208036"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"J. W\u00e4stlund,\n                      Random matching problems on the complete graph\n                      , Electron. Commun. Probab. (2008), pp. 258-265.","DOI":"10.1214\/ECP.v13-1372"},{"key":"atypb40","unstructured":"J. W\u00e4stlund,\n                      A simple proof of the Parisi and Coppersmith-Sorkin formulas for the random assignment problem\n                      , in Link\u00f6ping Studies in Mathematics, No. 6, Link\u00f6ping University Electronic Press, Link\u00f6ping, Sweden, 2005."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v14-1475"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.2307\/3620251"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1335418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:35Z","timestamp":1787319875000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1335418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1335418"],"URL":"https:\/\/doi.org\/10.1137\/20m1335418","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}