{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T15:47:01Z","timestamp":1787586421867,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    Given a graph G=(V,E) with n vertices, m edges, and a family of $\\kappa$ pairs of vertices in V, we are interested in finding for each pair (a\n                    <jats:sub>i<\/jats:sub>\n                    , b\n                    <jats:sub>i<\/jats:sub>\n                    ) a path connecting a\n                    <jats:sub>i<\/jats:sub>\n                    to b\n                    <jats:sub>i<\/jats:sub>\n                    such that the set of $\\kappa$ paths so found is edge disjoint. (For arbitrary graphs the problem is ${\\cal NP}$-complete, although it is in ${\\cal P}$ if $\\kappa$ is fixed.)\n                  <\/jats:p>\n                  <jats:p>\n                    We present a polynomial time randomized algorithm for finding the optimal number of edge disjoint paths (up to constant factors) in the random graph G\n                    <jats:sub>n,m<\/jats:sub>\n                    for all edge densities above the connectivity threshold. (The graph is chosen first; then an adversary chooses the pairs of endpoints.) Our results give the first tight bounds for the edge-disjoint paths problem for any nontrivial class of graphs.\n                  <\/jats:p>","DOI":"10.1137\/s0097539795290805","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"541-573","source":"Crossref","is-referenced-by-count":36,"title":["Optimal Construction of Edge-Disjoint Paths in Random Graphs"],"prefix":"10.1137","volume":"28","author":[{"given":"Andrei Z.","family":"Broder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan M.","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Suen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Michael Molloy, The probabilistic method, Algorithms Combin., Vol. 16, Springer, Berlin, 1998, 1\u2013351678558","DOI":"10.1007\/978-3-662-12788-9_1"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"R4","unstructured":"B. Bollob\u00e1s, Martingales, isoperimetric inequalities and random graphs, Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 52, North\u2010Holland, Amsterdam, 1988, 113\u201313994g:05075"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s, T. I. Fenner, and A. Frieze,\n                      Hamilton cycles in random graphs with minimal degree at least k\n                      , in \u201cA Tribute to Paul Erd\u00f6s,\u201d A. Baker, B. Bollob\u00e1s, and A. Hajnal, eds., Cambridge University Press, Cambridge, England, 1990, pp. 59\u201396.","DOI":"10.1017\/CBO9780511983917.006"},{"key":"R6","unstructured":", Graph theory with applications to algorithms and computer science, Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4\u20138, 1984, A Wiley\u2010Interscience Publication, John Wiley & Sons Inc., 1985, 0\u20130, xv+81086g:05026"},{"key":"R7","unstructured":"Andrei Broder, Alan Frieze, Stephen Suen, Eli Upfal, An efficient algorithm for the vertex\u2010disjoint paths problem in random graphs, ACM, New York, 1996, 261\u201326896k:05179"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792232021"},{"key":"R9","first-page":"609","volume":"11","author":"Erd\u00f6s P.","year":"1975","journal-title":"Colloq. Math. Soc. J\u00e1nos Bolyai","ISSN":"https:\/\/id.crossref.org\/issn\/0139-3383","issn-type":"print"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Friedman, J. Kahn, and E. Szemer\u00e9di,\n                      On the second eigenvalue in random regular graphs\n                      , in Proc. 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May 1989, pp. 587\u2013598.","DOI":"10.1145\/73007.73063"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.1073"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.5.923"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Kleinberg and \u00c9. Tardos,\n                      Approximations for the disjoint paths problem in high\u2010diameter planar networks\n                      , in Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 26\u201335.","DOI":"10.1145\/225058.225075"},{"key":"R14","unstructured":"Colin McDiarmid, On the method of bounded differences, London Math. Soc. Lecture Note Ser., Vol. 141, Cambridge Univ. Press, Cambridge, 1989, 148\u201318891e:05077"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0218015"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"R17","first-page":"141","volume":"24","author":"Shamir E.","year":"1985","journal-title":"Ann. Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-5060","issn-type":"print"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"L. G. Valiant and G. J. Brebner,\n                      Universal schemes for parallel communication\n                      , in Proc. 13th Annual ACM Symposium on Theory of Computation, Milwaukee, WI, May 1981, pp. 263\u2013277.","DOI":"10.1145\/800076.802479"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795290805","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:42Z","timestamp":1787336562000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795290805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795290805"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795290805","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}