{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:25:02Z","timestamp":1775039102111,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0830645 and CCF-1218916"],"award-info":[{"award-number":["CCF-0830645 and CCF-1218916"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>We present a suite of fast and effective algorithms, encapsulated in a software package called ColPack, for a variety of graph coloring and related problems. Many of the coloring problems model partitioning needs arising in compression-based computation of Jacobian and Hessian matrices using Algorithmic Differentiation. Several of the coloring problems also find important applications in many areas outside derivative computation, including frequency assignment in wireless networks, scheduling, facility location, and concurrency discovery and data movement operations in parallel and distributed computing. The presentation in this article includes a high-level description of the various coloring algorithms within a common design framework, a detailed treatment of the theory and efficient implementation of known as well as new vertex ordering techniques upon which the coloring algorithms rely, a discussion of the package's software design, and an illustration of its usage. The article also includes an extensive experimental study of the major algorithms in the package using real-world as well as synthetically generated graphs.<\/jats:p>","DOI":"10.1145\/2513109.2513110","type":"journal-article","created":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T18:14:28Z","timestamp":1380651268000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":58,"title":["ColPack"],"prefix":"10.1145","volume":"40","author":[{"given":"Assefaw H.","family":"Gebremedhin","sequence":"first","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Duc","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Md. Mostofa Ali","family":"Patwary","sequence":"additional","affiliation":[{"name":"Northwestern University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Pothen","sequence":"additional","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,10,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","DOI":"10.37236\/1779","article-title":"Coloring with no 2-colored P4's","volume":"11","author":"Albertson M.","year":"2004","journal-title":"Electron. J. Combinatorics"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69384-0_92"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Boisvert R. F. Pozo R. and Remington K. A. 1996. The Matrix Market formats: Initial Design. http:\/\/math.nist.gov\/MatrixMarket\/formats.html&num; MMformat.  Boisvert R. F. Pozo R. and Remington K. A. 1996. The Matrix Market formats: Initial Design. http:\/\/math.nist.gov\/MatrixMarket\/formats.html&num; MMformat.","DOI":"10.6028\/NIST.IR.5935"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90077-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080732158"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.08.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2012.07.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(81)90048-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0607026"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1271.1610"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/6187.6190"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0720013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612334"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595295349"},{"key":"e_1_2_1_17_1","unstructured":"Culberson J. C. 1992. Iterated greedy graph coloring and the difficulty landscape. Tech. rep. TR 92-07 Department of Computing Science University of Alberta Edmonton Alberta Canada.  Culberson J. C. 1992. Iterated greedy graph coloring and the difficulty landscape. Tech. rep. TR 92-07 Department of Computing Science University of Alberta Edmonton Alberta Canada."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/13.1.117"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063396"},{"key":"e_1_2_1_21_1","unstructured":"Diestel R. 2000. Graph Theory 2nd Ed. Springer New York.  Diestel R. 2000. Graph Theory 2nd Ed. Springer New York."},{"key":"e_1_2_1_22_1","unstructured":"Duff I. S. 1992. User's guide for the Harwell-Boeing sparse matrix collection. http:\/\/math.nist.gov\/MatrixMarket\/formats.html&num;hb.  Duff I. S. 1992. User's guide for the Harwell-Boeing sparse matrix collection. http:\/\/math.nist.gov\/MatrixMarket\/formats.html&num;hb."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020444"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19690390415"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504444711"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0286"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Gebremedhin A. Pothen A. and \n      \n      \n      Walther A\n      \n  \n  . \n  2008\n  . Exploiting sparsity in Jacobian computation via coloring and automatic differentiation: A case study in a Simulated Moving Bed process. In Advances in Automatic Differentiation C. Bischof et al. Ed. Lecture Notes in Computational Science and Engineering vol. \n  64 Springer 339--349.  Gebremedhin A. Pothen A. and Walther A. 2008. Exploiting sparsity in Jacobian computation via coloring and automatic differentiation: A case study in a Simulated Moving Bed process. In Advances in Automatic Differentiation C. Bischof et al. Ed. Lecture Notes in Computational Science and Engineering vol. 64 Springer 339--349.","DOI":"10.1007\/978-3-540-68942-3_29"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/050639879"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/229473.229474"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717761"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms. 620--629","author":"Hall J."},{"key":"e_1_2_1_32_1","volume-title":"SIAM Workshop on Combinatorial Scientific Computing.","author":"Hasan M."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805700"},{"key":"#cr-split#-e_1_2_1_34_1.1","doi-asserted-by":"crossref","unstructured":"Hossain S. and Steihaug T. 2012. Optimal direct determination of sparse Jacobian matrices. Optimization Meth. Softw. DOI:10.1080\/10556788.2012.693927. 10.1080\/10556788.2012.693927","DOI":"10.1080\/10556788.2012.693927"},{"key":"#cr-split#-e_1_2_1_34_1.2","doi-asserted-by":"crossref","unstructured":"Hossain S. and Steihaug T. 2012. Optimal direct determination of sparse Jacobian matrices. Optimization Meth. Softw. DOI:10.1080\/10556788.2012.693927.","DOI":"10.1080\/10556788.2012.693927"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90004-3"},{"key":"e_1_2_1_36_1","unstructured":"Karypis G. and Kumar V. 1998. MeTiS: A software package for partitioning unstructured graphs partitioning meshes and computing fill-reducing orderings of sparse matrices. http:\/\/people.sc. fsu.edu\/&sim;burkardt\/data\/metis_graph\/metis_graph.html.  Karypis G. and Kumar V. 1998. MeTiS: A software package for partitioning unstructured graphs partitioning meshes and computing fill-reducing orderings of sparse matrices. http:\/\/people.sc. fsu.edu\/&sim;burkardt\/data\/metis_graph\/metis_graph.html."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012311216333"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_1_39_1","first-page":"481","article-title":"A max-min theorem for graphs with application to graph coloring","volume":"10","author":"Matula D.","year":"1968","journal-title":"SIAM Rev."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Matula D. Marble G. and Isaacson J. 1972. Graph coloring algorithms. In Graph Theory and Computing R. Read Ed. Academic Press New York 109--122.  Matula D. Marble G. and Isaacson J. 1972. Graph coloring algorithms. In Graph Theory and Computing R. Read Ed. Academic Press New York 109--122.","DOI":"10.1016\/B978-1-4832-3187-7.50015-5"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592052"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759077"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2010.04.206"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Naumann U. 2012. The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation. Software Environments and Tools. SIAM Philadelphia PA.   Naumann U. 2012. The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation. Software Environments and Tools. SIAM Philadelphia PA.","DOI":"10.1137\/1.9781611972078"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Patwary M. M. A. Gebremedhin A. H. and \n      \n      \n      Pothen A\n      \n  \n  . \n  2011\n  . New multithreaded ordering and coloring algorithms for multicore architectures. In Proceedings of the International Euro-Par Conference on Parallel Processing. E. Jeannot R. Namyst and J. Roman Eds. Lecture Notes in Computer Science vol. \n  6853 Springer 250--262.   Patwary M. M. A. Gebremedhin A. H. and Pothen A. 2011. New multithreaded ordering and coloring algorithms for multicore architectures. In Proceedings of the International Euro-Par Conference on Parallel Processing. E. Jeannot R. Namyst and J. Roman Eds. Lecture Notes in Computer Science vol. 6853 Springer 250--262.","DOI":"10.1007\/978-3-642-23397-5_24"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716078"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0917054"},{"key":"e_1_2_1_48_1","first-page":"163","article-title":"Probing methods for generalized saddle-point problems","volume":"22","author":"Siefert C.","year":"2006","journal-title":"Electron. Trans. Numer. Anal."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80081-X"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90005-3"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1201\/b11644-8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2513109.2513110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2513109.2513110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:25Z","timestamp":1750232065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2513109.2513110"}},"subtitle":["Software for graph coloring and related problems in scientific computing"],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2513109.2513110"],"URL":"https:\/\/doi.org\/10.1145\/2513109.2513110","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}