{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:47:05Z","timestamp":1787496425075,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,6,21]],"date-time":"2014-06-21T00:00:00Z","timestamp":1403308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,6,21]]},"DOI":"10.1145\/2612669.2612697","type":"proceedings-article","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T10:23:03Z","timestamp":1404210183000},"page":"166-177","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Ordering heuristics for parallel graph coloring"],"prefix":"10.1145","author":[{"given":"William","family":"Hasenplaugh","sequence":"first","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Kaler","sequence":"additional","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao B.","family":"Schardl","sequence":"additional","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,6,21]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"ICPP","author":"Adams L.","year":"1982","unstructured":"L. Adams and J. Ortega . A multi-color SOR method for parallel computation . In ICPP , 1982 . L. Adams and J. Ortega. A multi-color SOR method for parallel computation. In ICPP, 1982."},{"key":"e_1_3_2_1_2_1","volume-title":"A comparison of parallel graph coloring algorithms. Technical report","author":"Allwright J. R.","year":"1995","unstructured":"J. R. Allwright , R. Bordawekar , P. D. Coddington , K. Dincer , and C. L. Martin . A comparison of parallel graph coloring algorithms. Technical report , Northeast Parallel Architecture Center , Syracuse University , 1995 . J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C. L. Martin. A comparison of parallel graph coloring algorithms. Technical report, Northeast Parallel Architecture Center, Syracuse University, 1995."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"key":"e_1_3_2_1_5_1","unstructured":"L. Barenboim and M. Elkin. Distributed (\u0394  L. Barenboim and M. Elkin. Distributed (\u0394"},{"key":"e_1_3_2_1_6_1","volume-title":"ACM STOC","year":"2009","unstructured":"1)$-coloring in linear (in \u0394) time. In ACM STOC , 2009 . 1)$-coloring in linear (in \u0394) time. In ACM STOC, 2009."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253263"},{"key":"e_1_3_2_1_8_1","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"Bertsekas D. P.","year":"1989","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis . Parallel and Distributed Computation: Numerical Methods . Prentice-Hall , 1989 . D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1989."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_1_15_1","volume-title":"CoRR","author":"\u00c7ataly\u00fcrek V.","year":"2012","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek , J. Feo , A. H. Gebremedhin , M. Halappanavar , and A. Pothen . Graph coloring algorithms for muti-core and massively multithreaded architectures . CoRR , 2012 . \u00dc. V. \u00c7ataly\u00fcrek, J. Feo, A. H. Gebremedhin, M. Halappanavar, and A. Pothen. Graph coloring algorithms for muti-core and massively multithreaded architectures. CoRR, 2012."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806984"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(81)90048-5"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_1_20_1","author":"Coleman T.","year":"1983","unstructured":"T. Coleman and J. Mor\u00e9 . Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal. , 1983 . T. Coleman and J. Mor\u00e9. Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal., 1983.","journal-title":"SIAM J. Numer. Anal."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463822.1463838"},{"key":"e_1_3_2_1_22_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms . The MIT Press , third edition, 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, third edition, 2009."},{"key":"e_1_3_2_1_23_1","volume-title":"Mathematical Foundations of Computer Science.","author":"Diks K.","year":"1986","unstructured":"K. Diks . A fast parallel algorithm for six-colouring of planar graphs . In Mathematical Foundations of Computer Science. 1986 . K. Diks. A fast parallel algorithm for six-colouring of planar graphs. In Mathematical Foundations of Computer Science. 1986."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167145"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.21127"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2754264.2754269"},{"key":"e_1_3_2_1_27_1","volume-title":"Theoretical Computer Science","author":"Garey M.","year":"1976","unstructured":"M. Garey , D. Johnson , and L. Stockmeyer . Some simplified NP-complete graph problems . Theoretical Computer Science , 1976 . M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1976."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/1096-9128(200010)12:12<1131::AID-CPE528>3.0.CO;2-2"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513109.2513110"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0117"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218029"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_3_2_1_34_1","volume-title":"The Art of Multiprocessor Programming","author":"Herlihy M.","year":"2008","unstructured":"M. Herlihy and N. Shavit . The Art of Multiprocessor Programming . Morgan Kaufmann Publishers Inc ., 2008 . M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., 2008."},{"key":"e_1_3_2_1_35_1","volume-title":"Intel Cilk Plus. Available fromtexttthttp:\/\/software.intel.com","year":"2013","unstructured":"Intel. Intel Cilk Plus. Available fromtexttthttp:\/\/software.intel.com , 2013 . Intel. Intel Cilk Plus. Available fromtexttthttp:\/\/software.intel.com, 2013."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914041"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90004-3"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612673"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_3_2_1_41_1","volume-title":"SNAP: Stanford Network Analysis Platform. Available from http:\/\/snap.stanford.edu\/data\/index.html","author":"Leskovec J.","year":"2013","unstructured":"J. Leskovec . SNAP: Stanford Network Analysis Platform. Available from http:\/\/snap.stanford.edu\/data\/index.html , 2013 . J. Leskovec. SNAP: Stanford Network Analysis Platform. Available from http:\/\/snap.stanford.edu\/data\/index.html, 2013."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90096-4"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_45_1","volume-title":"Students Conf.","author":"Marx D.","year":"2004","unstructured":"D. Marx . Graph colouring problems and their applications in scheduling. John von Neumann Ph.D . Students Conf. , 2004 . D. Marx. Graph colouring problems and their applications in scheduling. John von Neumann Ph.D. Students Conf., 2004."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/19.2.182"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800015.808204"},{"key":"e_1_3_2_1_49_1","volume-title":"A basic toolkit for sparse matrix computations","author":"Saad Y.","year":"1990","unstructured":"Y. Saad . SPARSKIT : A basic toolkit for sparse matrix computations . Research Institute for Advanced Computer Science, NASA Ames Research Center , 1990 . Y. Saad. SPARSKIT: A basic toolkit for sparse matrix computations. Research Institute for Advanced Computer Science, NASA Ames Research Center, 1990."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2011.6152726"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_3_2_1_52_1","author":"Welsh D. J. A.","year":"1967","unstructured":"D. J. A. Welsh and M. B. Powell . An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal , 1967 . D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 1967.","journal-title":"The Computer Journal"}],"event":{"name":"SPAA '14: 26th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Prague Czech Republic","acronym":"SPAA '14","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture"]},"container-title":["Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2612669.2612697","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2612669.2612697","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:01:34Z","timestamp":1750215694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2612669.2612697"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,21]]},"references-count":51,"alternative-id":["10.1145\/2612669.2612697","10.1145\/2612669"],"URL":"https:\/\/doi.org\/10.1145\/2612669.2612697","relation":{},"subject":[],"published":{"date-parts":[[2014,6,21]]},"assertion":[{"value":"2014-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}