{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T13:37:42Z","timestamp":1773149862201,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540651420","type":"print"},{"value":"9783540495437","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_1","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"1-14","source":"Crossref","is-referenced-by-count":6,"title":["Disjoint Paths in Expander Graphs via Random Walks: a Short Survey"],"prefix":"10.1007","author":[{"given":"Alan M.","family":"Frieze","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986) 83\u201396.","journal-title":"Combinatorica"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1137\/S0097539792232021","volume":"23","author":"A. Z. Broder","year":"1994","unstructured":"A. Z. Broder, A. M. Frieze and E. Upfal, Existence and construction of edge-disjoint paths on expander graphs, SIAM Journal of Computing 23 (1994) 976\u2013989.","journal-title":"SIAM Journal of Computing"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"A. Z. Broder, A.M. Frieze and E. Upfal, Existence and construction of edge low congestion paths on expander graphs, Proceedings of the 29th Annual ACM Symposium on Theory of Computing, (1997) 531\u2013539.","DOI":"10.1145\/258533.258646"},{"key":"1_CR4","unstructured":"A. Z. Broder, A. M. Frieze, S. Suen and E. Upfal, Optimal construction of edge disjoint paths in random graphs, Proceedings of 4th Annual Symposium on Discrete Algorithms, (1994) 603\u2013612."},{"key":"1_CR5","unstructured":"A. Z. Broder, A. M. Frieze, S. Suen and E. Upfal, An efficient algorithm for the vertex-disjoint paths problem in random graphs, Proceedings of 6th Annual Symposium on Discrete Algorithms, (1996) 261\u2013268."},{"key":"1_CR6","unstructured":"P. Erd\u00f6s and L. Lov\u00e1sz, Problems and results on 3-chromatic hypergraphs and some related questions, In A. Hajnal et al., editors, Infinite and Finite Sets, Volume 11 of Colloq. Math. Soc. J. Bolyai (1975)609\u2013627."},{"key":"1_CR7","unstructured":"A. Frank, Packing paths, cuts and circuits-a survey, in Paths, Flows and VLSI Layout, B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel and A. Schrijver Eds., Springer-Verlag, 1990."},{"key":"1_CR8","unstructured":"A. M. Frieze and M. Molloy, Splitting expanders."},{"key":"1_CR9","unstructured":"A. M. Frieze and L. Zhao, Edge disjoint paths in random regular graphs."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"J. Kleinberg and R. Rubinfeld, Short paths in expander graphs, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, (1996) 86\u201395.","DOI":"10.1109\/SFCS.1996.548467"},{"key":"1_CR11","unstructured":"T. Leighton and S. Rao, Circuit switching: amulticommodity flowbased approach, Proceedings of a Workshop on Randomized Parallel Computing 1996."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"T. Leighton, S. Rao and A. Srinivasan, Multi-commodity flow and circuit switching, Proceedings of the Hawaii International Conference on System Sciences, 1998.","DOI":"10.1109\/HICSS.1998.649241"},{"key":"1_CR13","unstructured":"T. Leighton, S. Rao and A. Srinivasan, New algorithmic aspects of the local lemma with applications to partitioning and routing."},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotsky","year":"1988","unstructured":"A. Lubotsky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261\u2013277.","journal-title":"Combinatorica"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF02125897","volume":"9","author":"D. Peleg","year":"1989","unstructured":"D. Peleg and E. Upfal, Constructing disjoint paths on expander graphs, Combinatorica, 9, (1989) 289\u2013313.","journal-title":"Combinatorica"},{"key":"1_CR16","unstructured":"N. Robertson and P.D. Seymour, Graph minors-XIII: The disjoint paths problem."},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A. Sinclair","year":"1989","unstructured":"A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation 82(1) (1989) 93\u2013133.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:21:10Z","timestamp":1737076870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}