{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T00:04:59Z","timestamp":1651622699670},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2004,12,31]]},"abstract":"We conduct an experimental analysis of a distributed randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly [Grable and Panconesi 1997]. We test the algorithm on a number of random as well as nonrandom graph families.The test cases were chosen based on two objectives: (i) to provide insights into the worst-case behavior (in terms of time and quality) of the algorithm and (ii) to test the performance of the algorithm with instances that are likely to arise in practice. Our main results include the following:(1) The empirical results obtained compare very well with the recent empirical results reported by other researchers [Durand et al. 1994, 1998; Jain and Werth 1995].(2) The empirical results confirm the bounds on the running time and the solution quality as claimed in the theoretical paper. Our results show that for certain classes of graphs the algorithm is likely to perform much better than the analysis suggests.(3) The results demonstrate that the algorithm might be well suited (from a theoretical as well as practical standpoint) for edge coloring graphs quickly and efficiently in a distributed setting.Based on our empirical study, we propose a simple modification of the original algorithm with substantially improved performance in practice.<\/jats:p>","DOI":"10.1145\/1005813.1041515","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"source":"Crossref","is-referenced-by-count":7,"title":["An experimental study of a simple, distributed edge-coloring algorithm"],"prefix":"10.1145","volume":"9","author":[{"given":"Madhav V.","family":"Marathe","sequence":"first","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos NM"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Universit\u00e1 La Sapienza di Roma, Roma Italy"}]},{"suffix":"jr","given":"Larry D.","family":"Risinger","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos NM"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0304-3975(98)00022-X","article-title":"Nearly-optimal, distributed edge-coloring via the nibble method","volume":"203","author":"Dubhashi D.","year":"1998","journal-title":"TCS"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Durand D. Jain R. and Tseytlin D. 1994. Distributed Scheduling Algorithms to Improve the Performance of Parallel Data Transfers. In ACM SIGARCH Computer Architecture News. ACM Press 35--40. Special issue on Input\/Output in Parallel Computer Systems. 10.1145\/190787.190799 Durand D. Jain R. and Tseytlin D. 1994. Distributed Scheduling Algorithms to Improve the Performance of Parallel Data Transfers. In ACM SIGARCH Computer Architecture News. ACM Press 35--40. Special issue on Input\/Output in Parallel Computer Systems. 10.1145\/190787.190799","DOI":"10.1145\/190787.190799"},{"key":"e_1_2_1_3_1","first-page":"225","article-title":"Applying randomized edge-coloring algorithms to distributed communications: An experimental study","volume":"203","author":"Durand D.","year":"1998","journal-title":"TCS"},{"key":"e_1_2_1_4_1","unstructured":"Ferrell R. Kothe D. and Turner J. 1997. PGSLib: A library for portable parallel unstructured mesh simulations. In Presented at the 8th SIAM Conference on Parallel Processing for Scientific Computing. Ferrell R. Kothe D. and Turner J. 1997. PGSLib: A library for portable parallel unstructured mesh simulations. In Presented at the 8th SIAM Conference on Parallel Processing for Scientific Computing."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Thirteenth ACM-SIAM Symposium on Discrete Algorithms (SODA 02)","author":"Finocchi I."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0211009","article-title":"Algorithms for edge-coloring bipartite graphs and multigraphs","volume":"1","author":"Gabow H.","year":"1982","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_7_1","first-page":"278","volume-title":"Also In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Grable D.","year":"1997"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Hochbaum D. Eds. 1997. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company Boston MA. Hochbaum D. Eds. 1997. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company Boston MA.","DOI":"10.1145\/261342.571216"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","article-title":"The NP-completeness of edge colorings","volume":"10","author":"Hoyler I.","year":"1980","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_10_1","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 R.","year":"1992","journal-title":"J. Parallel Distrib. Comput."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Jain R. Werth J. Browne J. and Sasaki G. 1992b. A graph-theoretic model for the scheduling problem and its application to simultaneous resource scheduling. In Computer Science and Operations Research: New Developments in Their Interfaces. O. Balci R. Shander and S. Zerrick Eds. Penguin Press. Jain R. Werth J. Browne J. and Sasaki G. 1992b. A graph-theoretic model for the scheduling problem and its application to simultaneous resource scheduling. In Computer Science and Operations Research: New Developments in Their Interfaces. O. Balci R. Shander and S. Zerrick Eds. Penguin Press.","DOI":"10.1016\/B978-0-08-040806-4.50027-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00013-3"},{"key":"e_1_2_1_13_1","unstructured":"Kothe D. Ferrell R. Turner J. and Mosso S. 1997. A high resolution finite volume method for efficient parallel simulation of casting processes on unstructured meshes. In Presented at the 8th SIAM Conference on Parallel Processing for Scientific Comput. LANL Report LA-UR-97-30 14--17. Kothe D. Ferrell R. Turner J. and Mosso S. 1997. A high resolution finite volume method for efficient parallel simulation of casting processes on unstructured meshes. In Presented at the 8th SIAM Conference on Parallel Processing for Scientific Comput. LANL Report LA-UR-97-30 14--17."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/135419.135465"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1005813.1041515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T21:55:48Z","timestamp":1613598948000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005813.1041515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,31]]},"references-count":14,"alternative-id":["10.1145\/1005813.1041515"],"URL":"http:\/\/dx.doi.org\/10.1145\/1005813.1041515","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2004,12,31]]}}}