Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds
Authors: Panconesi, Alessandro
Srinivasan, Aravind
Keywords: computer science
technical report
Issue Date: Jun-1993
Publisher: Cornell University
Abstract: Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge coloring a graph, in the synchronous distributed point-to-point model of computation. Our algorithms compute an edge-coloring of a graph $G$ with $n$ nodes and maximum degree $\Delta$ with at most $(1.6 + \epsilon)\Delta + \log^{2+\delta} n$ colors with high probability (arbitrarily close to 1), for any fixed $\epsilon,\delta greater than 0$. To analyze the performance of our algorithms, we introduce an extension of the Chernoff-Hoeffding bounds, which are fundamental tools that are used very frequently in estimating tail probabilities. However, they assume stochastic independence among certain random variables, which may not always hold. Our results extend the Chernoff-Hoeffding bounds to certain types of random variables which are not stochastically independent. We believe that these results are of independent interest, and merit further study.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
93-1357.pdf1.77 MBAdobe PDFView/Open
93-1357.ps421.88 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us