{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T17:55:34Z","timestamp":1784829334835,"version":"3.55.0"},"reference-count":26,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1998,8,1]],"date-time":"1998-08-01T00:00:00Z","timestamp":901929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5464,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1998,8]]},"DOI":"10.1016\/s0304-3975(98)00022-x","type":"journal-article","created":{"date-parts":[[2003,4,23]],"date-time":"2003-04-23T19:53:40Z","timestamp":1051127620000},"page":"225-251","source":"Crossref","is-referenced-by-count":38,"title":["Near-optimal, distributed edge colouring via the nibble method"],"prefix":"10.1016","volume":"203","author":[{"given":"Devdatt","family":"Dubhashi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David A.","family":"Grable","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(98)00022-X_BIB1","unstructured":"N. Alon, private communications."},{"key":"10.1016\/S0304-3975(98)00022-X_BIB2","doi-asserted-by":"crossref","unstructured":"N. Alon, J.H. Kim, J. Spencer, Nearly perfect matchings in regular simple hypergraphs, Israeli J. Math, to appear.","DOI":"10.1007\/BF02773639"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB3","article-title":"The Probabilistic Method","author":"Alon","year":"1992"},{"issue":"4","key":"10.1016\/S0304-3975(98)00022-X_BIB4","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1145\/115234.115347","article-title":"Simulating (logc n)-wise Independence in NC","volume":"38","author":"Berger","year":"1991","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB5","series-title":"Graph Theory","author":"Bollob\u00e1s","year":"1979"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB6","series-title":"LATIN'95: Theoretical Informatics, 2nd Latin American Symposium","first-page":"207","article-title":"Probabilistic recurrence relations","author":"Chaudhuri","year":"1955"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB7","series-title":"Proc. Symp. on Parallel Algorithms and Architectures","first-page":"264","article-title":"Applying randomized edge coloring algorithms to distributed communication: an experimental study","author":"Durand","year":"1995"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0195-6698(85)80045-7","article-title":"Near perfect coverings in graphs and hypergraphs","volume":"6","author":"Frankl","year":"1985","journal-title":"European J. Combin."},{"key":"10.1016\/S0304-3975(98)00022-X_BIB9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","article-title":"NP-completeness of finding the chromatic index of regular graphs","volume":"4","author":"Galil","year":"1983","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB10","doi-asserted-by":"crossref","unstructured":"D.A. Grable, A large deviation inequality for functions of independent, multi-way choices, Combinatorics, Probab. Comput., to appear.","DOI":"10.1017\/S0963548397003246"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB11","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","article-title":"The NP-completeness of edge coloring","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/S0304-3975(98)00022-X_BIB12","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0743-7315(92)90018-I","article-title":"Scheduling parallel I\/O operations in multiple bus systems","volume":"16","author":"Jain","year":"1992","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/S0304-3975(98)00022-X_BIB13","unstructured":"O. Johansson, Randomized distributed graph coloring in logarithmic time, manuscript."},{"key":"10.1016\/S0304-3975(98)00022-X_BIB14","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0097-3165(92)90096-D","article-title":"Colouring nearly-disjoint hypergraphs with n + o(n) colors","volume":"59","author":"Kahn","year":"1992","journal-title":"J. Combin. Theory. Ser. A"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB15","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","article-title":"Efficient parallel algorithms for edge coloring problems","volume":"8","author":"Karloff","year":"1987","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB16","series-title":"23rd STOC","first-page":"190","article-title":"Probabilistic Recurrence Relations","author":"Karp","year":"1991"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB17","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1002\/rsa.3240070302","article-title":"The Ramsey number R(3, t) has order of magnitude t2\/log t","volume":"7","author":"Kim","year":"1995","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB18","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(81)90015-5","article-title":"Upper bounds for static resource allocation in a distributed system","volume":"23","author":"Lynch","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(98)00022-X_BIB19","series-title":"Surveys in Combinatorics","first-page":"148","article-title":"On the method of bounded differences","volume":"vol. 141","author":"McDiarmid","year":"1989"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB20","series-title":"Proc. 30th FOCS","first-page":"8","article-title":"The probabilistic method yields deterministic parallel algorithms","author":"Motwani","year":"1989"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB21","series-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB22","series-title":"Preliminary version in Proc. PODC","first-page":"251","article-title":"Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds","author":"Panconesi","year":"1992"},{"issue":"2","key":"10.1016\/S0304-3975(98)00022-X_BIB23","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01200759","article-title":"The local nature of \u0394-colorings and its algorithmic applications","volume":"15","author":"Panconesi","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB24","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/0097-3165(89)90074-5","article-title":"Asymptotic behaviour of the chromatic index for hypergraphs","volume":"51","author":"Pippinger","year":"1989","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/S0304-3975(98)00022-X_BIB25","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0195-6698(85)80023-8","article-title":"On a packing and covering problem","volume":"5","author":"R\u00f6dl","year":"1985","journal-title":"European J. Combin."},{"issue":"2","key":"10.1016\/S0304-3975(98)00022-X_BIB26","doi-asserted-by":"crossref","first-page":"575","DOI":"10.2140\/pjm.1985.118.575","article-title":"Asymptotically good coverings","volume":"118","author":"Spencer","year":"1985","journal-title":"Pacific J. Math."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439759800022X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439759800022X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T09:01:39Z","timestamp":1555405299000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439759800022X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,8]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,8]]}},"alternative-id":["S030439759800022X"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(98)00022-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1998,8]]}}}