{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:59Z","timestamp":1725664259248},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540603139"},{"type":"electronic","value":"9783540449133"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60313-1_162","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:16:49Z","timestamp":1330280209000},"page":"448-459","source":"Crossref","is-referenced-by-count":2,"title":["Near-optimal distributed edge coloring"],"prefix":"10.1007","author":[{"given":"Devdatt","family":"Dubhashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"33_CR1","unstructured":"N. Alon. Private Communication."},{"key":"33_CR2","volume-title":"The Probabilistic Method. Wiley-Interscience Series","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. Spencer, and P. Erd\u0151s. The Probabilistic Method. Wiley-Interscience Series, John Wiley & Sons, Inc., New York, 1992."},{"issue":"4","key":"33_CR3","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1145\/115234.115347","volume":"38","author":"B. Berger","year":"1991","unstructured":"B. Berger and J. Rompel. Simulating (logc\nn)-wise independence in NC. J. Assoc. Comput. Mach., 38(4): 1026\u20131046, 1991.","journal-title":"J. Assoc. Comput. Mach."},{"key":"33_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9967-7","volume-title":"Graph Theory","author":"B. Bollob\u00e1s","year":"1979","unstructured":"B. Bollob\u00e1s. Graph Theory. Springer Verlag, New York, 1979."},{"key":"33_CR5","unstructured":"N.G. de Bruijn. Asymptotic methods in Analysis. Number 4 in Bibliotheca Mathematics. North Holland Publishing Co., 1958."},{"key":"33_CR6","unstructured":"R. Jain D. Durand and D. Tseytlin. Distributed scheduling algorithms to improve the performance of parallel data transfers. Technical Report 94-38, DIMACS, 1994."},{"key":"33_CR7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"Z. Galil","year":"1983","unstructured":"Z. Galil and D. Leven. NP-completeness of finding the chromatic index of regular graphs. J. of Algorithms, 4:35\u201344, 1983.","journal-title":"J. of Algorithms"},{"key":"33_CR8","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer. The NP-completeness of edge coloring. SIAM J. Comp., 10:718\u2013720, 1981.","journal-title":"SIAM J. Comp."},{"issue":"4","key":"33_CR9","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0743-7315(92)90018-I","volume":"16","author":"R. Jain","year":"1992","unstructured":"R. Jain, K. Somalwar, J. Werth, and J. C. Browne. Scheduling parallel i\/o operations in multiple bus systems. Journal of Parallel and Distributed Computing, 16(4):352\u2013362, 1992.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0097-3165(92)90096-D","volume":"59","author":"J. Kahn","year":"1992","unstructured":"J. Kahn. Coloring nearly-disjoint hypergraphs with n+ o(n) colors. J. Comb. Theory, Series A, 59:31\u201339, 1992.","journal-title":"J. Comb. Theory, Series A"},{"key":"33_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","volume":"8","author":"H. J. Karloff","year":"1987","unstructured":"H. J. Karloff and D. B. Shmoys. Efficient parallel algorithms for edge coloring problems. Journal of Algorithms, 8:39\u201352, 1987.","journal-title":"Journal of Algorithms"},{"key":"33_CR12","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Probabilistic recurrence relations. In Proceedings of the ACM Symposium on Theory of Computing, pages 190\u2013197, 1991.","DOI":"10.1145\/103418.103443"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"M. Luby. Removing randomness in parallel computation without a processor penalty. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 162\u2013173, 1988. To appear in a special issue of Journal of Computer and System Sciences, devoted to FOCS 1988.","DOI":"10.1109\/SFCS.1988.21934"},{"key":"33_CR14","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(81)90015-5","volume":"23","author":"N. A. Lynch","year":"1981","unstructured":"N. A. Lynch. Upper bounds for static resource allocation in a distributed system. Journal of Computer and System Sciences, 23:254\u2013278, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, volume 141 of London Math. Soc. Lecture Notes Series, pages 148\u2013188. Cambrideg University Press, 1989.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"R. Motwani, J. Naor, and M. Naor. The probabilistic method yields deterministic parallel algorithms. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 8\u201313, 1989.","DOI":"10.1109\/SFCS.1989.63448"},{"key":"33_CR17","doi-asserted-by":"crossref","unstructured":"A. Panconesi and A. Srinivasan. Fast randomized algorithms for distributed edge coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 251\u2013262, 1992.","DOI":"10.1145\/135419.135465"},{"key":"33_CR18","doi-asserted-by":"crossref","unstructured":"A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proceedings of the ACM Symposium on Theory of Computing, pages 581\u2013592, 1992.","DOI":"10.1145\/129712.129769"},{"key":"33_CR19","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/0097-3165(89)90074-5","volume":"51","author":"N. Pippinger","year":"1989","unstructured":"N. Pippinger and J. Spencer. Asymptotic behaviour of the chromatic index for hypergraphs. J. Combinatorial Theory, Series A, 51:24\u201342, 1989.","journal-title":"J. Combinatorial Theory, Series A"},{"key":"33_CR20","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0195-6698(85)80023-8","volume":"5","author":"V. R\u00f6dl","year":"1985","unstructured":"V. R\u00f6dl. On a packing and covering problem. European Journal of Combinatorics, 5:69\u201378, 1985.","journal-title":"European Journal of Combinatorics"},{"issue":"2","key":"33_CR21","doi-asserted-by":"crossref","first-page":"575","DOI":"10.2140\/pjm.1985.118.575","volume":"118","author":"J. Spencer","year":"1985","unstructured":"J. Spencer. Asymptotically Good Coverings. Pacific Journal of Mathematics, 118(2):575\u2013586, 1985.","journal-title":"Pacific Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_162.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:37:07Z","timestamp":1619573827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-60313-1_162","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}