{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:42:14Z","timestamp":1703187734759},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,1,31]],"date-time":"2013-01-31T00:00:00Z","timestamp":1359590400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s00453-013-9749-4","type":"journal-article","created":{"date-parts":[[2013,1,30]],"date-time":"2013-01-30T15:28:03Z","timestamp":1359559683000},"page":"522-539","source":"Crossref","is-referenced-by-count":1,"title":["Thresholds for Extreme Orientability"],"prefix":"10.1007","volume":"69","author":[{"given":"Po-Shen","family":"Loh","sequence":"first","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,31]]},"reference":[{"key":"9749_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2007","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, New York (2007)","edition":"3"},{"key":"9749_CR2","first-page":"698","volume-title":"Proceedings of 25th International Parallel and Distributed Processing Symposium (IPDPS)","author":"R.R. Amossen","year":"2011","unstructured":"Amossen, R.R., Pagh, R.: A new data layout for set intersection on gpus. In: Proceedings of 25th International Parallel and Distributed Processing Symposium (IPDPS), pp. 698\u2013708. IEEE, New York (2011)"},{"issue":"1","key":"9749_CR3","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM J. Comput. 29(1), 180\u2013200 (1999)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9749_CR4","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1137\/S009753970444435X","volume":"35","author":"P. Berenbrink","year":"2006","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: the heavily loaded case. SIAM J. Comput. 35(6), 1350\u20131385 (2006)","journal-title":"SIAM J. Comput."},{"key":"9749_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/rsa.20343","volume":"38","author":"T. Bohman","year":"2011","unstructured":"Bohman, T., Frieze, A., Krivelevich, M., Loh, P.-S., Sudakov, B.: Ramsey games with giants. Random Struct. Algorithms 38, 1\u201332 (2011)","journal-title":"Random Struct. Algorithms"},{"key":"9749_CR6","first-page":"469","volume-title":"Proceedings of the 18th Symposium on Discrete Algorithms (SODA)","author":"J.A. Cain","year":"2007","unstructured":"Cain, J.A., Sanders, P., Wormald, N.: The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation. In: Proceedings of the 18th Symposium on Discrete Algorithms (SODA), pp. 469\u2013476. SIAM, Philadelphia (2007)"},{"key":"9749_CR7","first-page":"110","volume-title":"Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"M. Dietzfelbinger","year":"1993","unstructured":"Dietzfelbinger, M., auf der Heide, F.M.: Simple, efficient shared memory simulations. In: Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 110\u2013119 (1993). SIGACT and SIGARCH, Extended abstract"},{"key":"9749_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/978-3-642-14165-2_19","volume-title":"Proceedings of 37th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"M. Dietzfelbinger","year":"2010","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via xorsat. In: Proceedings of 37th International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 6198, pp. 213\u2013225 (2010)"},{"key":"9749_CR9","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17\u201361 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"9749_CR10","first-page":"459","volume-title":"Proceedings of the 18th Symposium on Discrete Algorithms (SODA)","author":"D. Fernholz","year":"2007","unstructured":"Fernholz, D., Ramachandran, V.: The k-orientability thresholds for g n,p . In: Proceedings of the 18th Symposium on Discrete Algorithms (SODA), pp. 459\u2013468. SIAM, Philadelphia (2007)"},{"key":"9749_CR11","first-page":"1222","volume-title":"Proceedings of the 22nd Symposium on Discrete Algorithms (SODA)","author":"N. Fountoulakis","year":"2011","unstructured":"Fountoulakis, N., Khosla, M., Panagiotou, K.: The multiple-orientability thresholds for random hypergraphs. In: Proceedings of the 22nd Symposium on Discrete Algorithms (SODA), pp. 1222\u20131236. SIAM, Philadelphia (2011)"},{"key":"9749_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/978-3-642-14165-2_30","volume-title":"Proceedings of 37th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"N. Fountoulakis","year":"2010","unstructured":"Fountoulakis, N., Panagiotou, K.: Orientability of random hypergraphs and the power of multiple choices. In: Proceedings of 37th International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 6198, pp. 348\u2013359. Springer, Berlin (2010)"},{"issue":"3","key":"9749_CR13","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1002\/rsa.20427","volume":"41","author":"A.M. Frieze","year":"2012","unstructured":"Frieze, A.M., Melsted, P.: Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Struct. Algorithms 41(3), 334\u2013364 (2012)","journal-title":"Random Struct. Algorithms"},{"key":"9749_CR14","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/1806689.1806705","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)","author":"P. Gao","year":"2010","unstructured":"Gao, P., Wormald, N.C.: Load balancing and orientability thresholds for random hypergraphs. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 97\u2013104. ACM, New York (2010)"},{"key":"9749_CR15","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., Luczak, T., Rucinski, A.: Random Graphs. Wiley, New York (2000)"},{"key":"9749_CR16","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0377-0427(01)00464-2","volume":"142","author":"M. Karo\u0144ski","year":"2002","unstructured":"Karo\u0144ski, M., Luczak, T.: The phase transition in a random hypergraph. J. Comput. Appl. Math. 142, 125\u2013135 (2002)","journal-title":"J. Comput. Appl. Math."},{"key":"9749_CR17","first-page":"251","volume-title":"Proceedings of the 23rd Symposium on Discrete Algorithms (SODA)","author":"M. Lelarge","year":"2012","unstructured":"Lelarge, M.: A new approach to the orientation of random hypergraphs. In: Proceedings of the 23rd Symposium on Discrete Algorithms (SODA), pp. 251\u2013264. SIAM, Philadelphia (2012)"},{"key":"9749_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9749_CR19","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51, 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"9749_CR20","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1998","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, New York (1998)"},{"issue":"2","key":"9749_CR21","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"Stockmeyer, L., Vishkin, U.: Simulation of parallel random access machines by circuits. SIAM J. Comput. 13(2), 409\u2013422 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9749_CR22","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/7531.7926","volume":"34","author":"E. Upfal","year":"1987","unstructured":"Upfal, E., Wigderson, A.: How to share memory in a distributed system. J. ACM 34(1), 116\u2013127 (1987)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9749-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9749-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9749-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:11Z","timestamp":1559137511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9749-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,31]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9749"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9749-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,31]]}}}