{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T10:34:09Z","timestamp":1762252449401,"version":"build-2065373602"},"reference-count":25,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3643,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/501100003763","name":"Minist\u00e8re des Affaires Etrang\u00e8res","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003763","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0166-218x(02)00424-9","type":"journal-article","created":{"date-parts":[[2003,9,3]],"date-time":"2003-09-03T11:09:00Z","timestamp":1062587340000},"page":"179-198","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":6,"title":["Graph coloring on coarse grained multicomputers"],"prefix":"10.1016","volume":"131","author":[{"given":"Assefaw Hadish","family":"Gebremedhin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isabelle Gu\u00e9rin","family":"Lassous","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Gustedt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00424-9_BIB1","unstructured":"J.R. Allwright, R. Bordawekar, P.D. Coddington, K. Dincer, C.L. Martin, A comparison of parallel graph coloring algorithms, Technical Report Technical Report SCCS-666, Northeast Parallel Architecture Center, Syracuse University, 1995."},{"key":"10.1016\/S0166-218X(02)00424-9_BIB2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","article-title":"Register allocation via coloring","volume":"6","author":"Chaitin","year":"1981","journal-title":"Comput. Languages"},{"key":"10.1016\/S0166-218X(02)00424-9_BIB3","series-title":"Mathematical Foundations of Computer Science 1989, Proceedings 14th Symposium","first-page":"185","article-title":"Parallel complexity of lexicographically first problems for tree-structured graphs","volume":"Vol. 379","author":"Chelbus","year":"1989"},{"issue":"1","key":"10.1016\/S0166-218X(02)00424-9_BIB4","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0720013","article-title":"Estimation of sparse Jacobian matrices and graph coloring problems","volume":"20","author":"Coleman","year":"1983","journal-title":"SIAM J. Numer. Anal."},{"key":"10.1016\/S0166-218X(02)00424-9_BIB5","doi-asserted-by":"crossref","unstructured":"D. Culler, R. Karp, D. Patterson, A. Sahay, K. Schauser, E. Santos, R. Subramonian, T. von Eicken, LogP: towards a realistic model of parallel computation, in: Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practises of Parallel Programming, San Diego, CA, 1993, pp. 1\u201312.","DOI":"10.1145\/155332.155333"},{"issue":"3","key":"10.1016\/S0166-218X(02)00424-9_BIB6","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1142\/S0218195996000241","article-title":"Scalable parallel computational geometry for coarse grained multicomputers","volume":"6","author":"Dehne","year":"1996","journal-title":"Internat. J. Comput. Geom."},{"key":"10.1016\/S0166-218X(02)00424-9_BIB7","doi-asserted-by":"crossref","unstructured":"S. Fortune, J. Wyllie, Parallelism in random access machines, in: 10th ACM Symposium on Theory of Computing, San Diego, CA, 1978, pp. 114\u2013118.","DOI":"10.1145\/800133.804339"},{"issue":"1","key":"10.1016\/S0166-218X(02)00424-9_BIB8","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/T-VT.1986.24063","article-title":"Some lower bounds for a class of frequency assignment problems","volume":"35","author":"Gamst","year":"1986","journal-title":"IEEE Trans. Vehicular Technol."},{"year":"1979","series-title":"Computers and Intractability","author":"Garey","key":"10.1016\/S0166-218X(02)00424-9_BIB9"},{"key":"10.1016\/S0166-218X(02)00424-9_BIB10","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1002\/1096-9128(200010)12:12<1131::AID-CPE528>3.0.CO;2-2","article-title":"Scalable parallel graph coloring algorithms","volume":"12","author":"Gebremedhin","year":"2000","journal-title":"Concurrency: Practice and Experience"},{"key":"10.1016\/S0166-218X(02)00424-9_BIB11","doi-asserted-by":"crossref","unstructured":"M. Goudreau, K. Lang, S. Rao, T. Suel, T. Tsantilas, Towards efficiency and portability: programming with the BSP model, in: Eighth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201996), Padua, Italy, 1996, pp. 1\u201312.","DOI":"10.1145\/237502.237503"},{"year":"1995","series-title":"Limits to Parallel Computation: P-Completeness Theory","author":"Greenlaw","key":"10.1016\/S0166-218X(02)00424-9_BIB12"},{"key":"10.1016\/S0166-218X(02)00424-9_BIB13","unstructured":"I. Gu\u00e9rin Lassous, J. Gustedt, M. Morvan, Feasability, portability, predictability and efficiency: four ambitious goals for the design and implementation of parallel coarse grained graph algorithms, Technical Report 3885, INRIA, 2000a."},{"key":"10.1016\/S0166-218X(02)00424-9_BIB14","series-title":"Recent Advances in Parallel Virtual Machine and Message Passing Interface, Seventh European PVM\/MPI Users\u2019 Group Meeting","first-page":"72","article-title":"Handling graphs according to a coarse grained approach: experiments with MPI and PVM","volume":"Vol. 1908","author":"Gu\u00e9rin Lassous","year":"2000"},{"issue":"1","key":"10.1016\/S0166-218X(02)00424-9_BIB15","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1137\/0403008","article-title":"Brooks coloring in parallel","volume":"3","author":"Hajnal","year":"1990","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"10.1016\/S0166-218X(02)00424-9_BIB16","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1137\/0914041","article-title":"A parallel graph coloring heuristic","volume":"14","author":"Jones","year":"1993","journal-title":"SIAM J. Scientific Comput."},{"issue":"1","key":"10.1016\/S0166-218X(02)00424-9_BIB17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0196-6774(88)90006-5","article-title":"A fast parallel algorithm to color a graph with D colors","volume":"9","author":"Karchmer","year":"1988","journal-title":"J. Algorithms"},{"issue":"1","key":"10.1016\/S0166-218X(02)00424-9_BIB18","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0304-3975(89)90121-7","article-title":"An NC algorithm for Brook's theorem","volume":"68","author":"Karloff","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00424-9_BIB19","doi-asserted-by":"crossref","unstructured":"R. Karp, V. Ramachandran, Parallel algorithms for shared-memory machines, in: Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, Elsevier, Amsterdam, 1990, pp. 869\u2013942.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"10.1016\/S0166-218X(02)00424-9_BIB20","unstructured":"G. Lewandowski, Practical implementations and applications of graph coloring, Ph.D. Thesis, University of Wisconsin-Madison, 1994."},{"issue":"4","key":"10.1016\/S0166-218X(02)00424-9_BIB21","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A simple parallel algorithm for the maximal independent set problem","volume":"15","author":"Luby","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00424-9_BIB22","doi-asserted-by":"crossref","unstructured":"F. Manne, A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices (extended abstract), in: Proceedings of Para98, Vol. 1541, Lecture Notes in Compouter Sciences, Springer, Berlin, 1998, pp. 332\u2013336.","DOI":"10.1007\/BFb0095354"},{"issue":"1","key":"10.1016\/S0166-218X(02)00424-9_BIB23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0020-0190(87)90092-5","article-title":"A fast parallel coloring of planar graphs with five colors","volume":"25","author":"Naor","year":"1987","journal-title":"Inform. Process. Lett."},{"issue":"8","key":"10.1016\/S0166-218X(02)00424-9_BIB24","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","article-title":"A bridging model for parallel computation","volume":"33","author":"Valiant","year":"1990","journal-title":"Comm. ACM"},{"issue":"5","key":"10.1016\/S0166-218X(02)00424-9_BIB25","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1109\/TC.1986.1676783","article-title":"New classes for parallel complexity","volume":"C-35","author":"Vitter","year":"1986","journal-title":"IEEE Trans. Comput."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004249?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004249?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T10:29:25Z","timestamp":1762252165000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02004249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0166218X02004249"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00424-9","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2003,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Graph coloring on coarse grained multicomputers","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0166-218X(02)00424-9","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2003 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}