{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:28:47Z","timestamp":1787333327621,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>The distance-2 graph coloring problem aims at partitioning the vertex set of a graph into the fewest sets consisting of vertices pairwise at distance greater than 2 from each other. Its applications include derivative computation in numerical optimization and channel assignment in radio networks. We present efficient, distributed-memory, parallel heuristic algorithms for this NP-hard problem as well as for two related problems used in the computation of Jacobians and Hessians. Parallel speedup is achieved through graph partitioning, speculative (iterative) coloring, and a bulk synchronous parallel\u2013like organization of parallel computation. Results from experiments conducted on a PC cluster employing up to 96 processors and using large-size real-world as well as synthetically generated test graphs show that the algorithms are scalable. In terms of quality of solution, the algorithms perform remarkably well\u2014the numbers of colors used by the parallel algorithms are observed to be very close to the numbers used by their sequential counterparts, which in turn are quite often near optimal. Moreover, the experimental results show that the parallel distance-2 coloring algorithm compares favorably with the alternative approach of solving the distance-2 coloring problem on a graph $\\mathcal{G}$ by first constructing the square graph $\\mathcal{G}^2$ and then applying a parallel distance-1 coloring algorithm on $\\mathcal{G}^2$. Implementations of the algorithms are made available via the Zoltan toolkit.<\/jats:p>","DOI":"10.1137\/080732158","type":"journal-article","created":{"date-parts":[[2010,8,5]],"date-time":"2010-08-05T18:13:42Z","timestamp":1281032022000},"page":"2418-2446","source":"Crossref","is-referenced-by-count":22,"title":["Distributed-Memory Parallel Algorithms for Distance-2 Coloring and Related Problems in Derivative Computation"],"prefix":"10.1137","volume":"32","author":[{"given":"Doruk","family":"Bozda\u011f","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmt V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Assefaw H.","family":"Gebremedhin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fredrik","family":"Manne","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik G.","family":"Boman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F\u00fcsun","family":"\u00d6zg\u00fcner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,8,5]]},"reference":[{"key":"R1","first-page":"41","volume":"100","author":"Agnarsson G.","year":"2000","journal-title":"Congr. Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0384-9864","issn-type":"print"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100367950"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358194"},{"key":"R4","unstructured":"R. H. Bisseling,\n                      Parallel Scientific Computation: A Structured Approach Using BSP and MPI\n                      , Oxford University Press, London, 2004."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"D. Bozda\u011f, U. Catalyurek, A. H. Gebremedhin, F. Manne, E. G. Boman, and F. \u00d6zg\u00fcner,\n                      A parallel distance-2 graph coloring algorithm for distributed memory computers\n                      , in Proceedings of HPCC 2005, Lecture Notes in Comput. Sci. 3726, Springer, New York, 2005, pp. 796\u2013806.","DOI":"10.1007\/11557654_90"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.08.002"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0720013"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612334"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/13.1.117"},{"key":"R11","unstructured":"T. Davis and Y. Hu, maintainers,\n                      University of Florida Sparse Matrix Collection\n                      , available at http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/5992.988653"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0286"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/1096-9128(200010)12:12<1131::AID-CPE528>3.0.CO;2-2"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. H. Gebremedhin, F. Manne, and A. Pothen,\n                      \n                        Parallel distance-\n                        k\n                        coloring algorithms for numerical optimization\n                      \n                      , in Proceedings of Euro-Par 2002, Lecture Notes in Comput. Sci. 2400, Springer, New York, 2002, pp. 912\u2013921.","DOI":"10.1007\/3-540-45706-2_130"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504444711"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/050639879"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500376193"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90004-3"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012311216333"},{"key":"R22","unstructured":"V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan,\n                      End-to-end packet-scheduling in wireless ad-hoc networks\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, SIAM, Philadelphia, pp. 1014\u20131023."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592052"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759077"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0716078"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0917054"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"M. M. Strout and P. D. Hovland,\n                      Metrics and models for reordering transformations\n                      , in Proceedings of the Second ACM SIGPLAN Workshop on Memory System Performance, 2004, ACM, New York, pp. 23\u201334.","DOI":"10.1145\/1065895.1065899"},{"key":"R29","unstructured":"The Second DIMACS Implementation Challenge: Maximum Clique, Graph Coloring, and Satisfiability\n                      , http:\/\/dimacs.rutgers.edu\/Challenges."},{"key":"R30","unstructured":"Georgia Tech College of Computing,\n                      GTgraph: A suite of synthetic graph generators\n                      , available at http:\/\/www-static.cc.gatech.edu\/~kamesh\/GTgraph\/."},{"key":"R31","unstructured":"The Zoltan Team,\n                      Zoltan: Parallel partitioning, load balancing and data-management services\n                      , software package available online at http:\/\/www.cs.sandia.gov\/Zoltan\/."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080732158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:51:18Z","timestamp":1787331078000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080732158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080732158"],"URL":"https:\/\/doi.org\/10.1137\/080732158","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}