Access Restriction

Author Marathe, Madhav V. ♦ Panconesi, Alessandro ♦ Risinger, Larry D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Distributed algorithms ♦ Edge coloring ♦ Experimental analysis of algorithms ♦ High performance computing ♦ Randomized algorithms ♦ Scheduling
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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 9

Open content in new tab

   Open content in new tab
Source: ACM Digital Library