Abstract
We give a distributed randomized algorithm to edge color a network. Given a graph G with n nodes and maximum degree Δ, the algorithm,
-
For any fixed λ>0, colours G with (1+λ)Δ colours in time O(log n).
-
For any fixed positive integer s, colours G with Δ+Δ/(log Δ)s=(1+o(1))Δ colours in time O(log n+logs Δ loglog Δ).
Both results hold with probability arbitrarily close to 1 as long as Δ(G) =Ω(log1+d n), for some d > 0. The algorithm is based on the Rödl Nibble, a probabilistic strategy introduced by Vojtech Rödl. The analysis involves a certain quasi-random phenomenon involving sets at the vertices of the graph.
Work done partly while at the Max-Planck-Institute für Informatik supported by the ESPRIT Basic Research Actions Program of the EC under contract No. 7141 (project ALCOM II).
Supported by an Ercim postdoctoral fellowship.
Basic Research in Computer Science, Centre of the Danish National Research Foundation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon. Private Communication.
N. Alon, J. Spencer, and P. Erdős. The Probabilistic Method. Wiley-Interscience Series, John Wiley & Sons, Inc., New York, 1992.
B. Berger and J. Rompel. Simulating (logc n)-wise independence in NC. J. Assoc. Comput. Mach., 38(4): 1026–1046, 1991.
B. Bollobás. Graph Theory. Springer Verlag, New York, 1979.
N.G. de Bruijn. Asymptotic methods in Analysis. Number 4 in Bibliotheca Mathematics. North Holland Publishing Co., 1958.
R. Jain D. Durand and D. Tseytlin. Distributed scheduling algorithms to improve the performance of parallel data transfers. Technical Report 94-38, DIMACS, 1994.
Z. Galil and D. Leven. NP-completeness of finding the chromatic index of regular graphs. J. of Algorithms, 4:35–44, 1983.
I. Holyer. The NP-completeness of edge coloring. SIAM J. Comp., 10:718–720, 1981.
R. Jain, K. Somalwar, J. Werth, and J. C. Browne. Scheduling parallel i/o operations in multiple bus systems. Journal of Parallel and Distributed Computing, 16(4):352–362, 1992.
J. Kahn. Coloring nearly-disjoint hypergraphs with n+ o(n) colors. J. Comb. Theory, Series A, 59:31–39, 1992.
H. J. Karloff and D. B. Shmoys. Efficient parallel algorithms for edge coloring problems. Journal of Algorithms, 8:39–52, 1987.
R. M. Karp. Probabilistic recurrence relations. In Proceedings of the ACM Symposium on Theory of Computing, pages 190–197, 1991.
M. Luby. Removing randomness in parallel computation without a processor penalty. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 162–173, 1988. To appear in a special issue of Journal of Computer and System Sciences, devoted to FOCS 1988.
N. A. Lynch. Upper bounds for static resource allocation in a distributed system. Journal of Computer and System Sciences, 23:254–278, 1981.
C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, volume 141 of London Math. Soc. Lecture Notes Series, pages 148–188. Cambrideg University Press, 1989.
R. Motwani, J. Naor, and M. Naor. The probabilistic method yields deterministic parallel algorithms. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 8–13, 1989.
A. Panconesi and A. Srinivasan. Fast randomized algorithms for distributed edge coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 251–262, 1992.
A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proceedings of the ACM Symposium on Theory of Computing, pages 581–592, 1992.
N. Pippinger and J. Spencer. Asymptotic behaviour of the chromatic index for hypergraphs. J. Combinatorial Theory, Series A, 51:24–42, 1989.
V. Rödl. On a packing and covering problem. European Journal of Combinatorics, 5:69–78, 1985.
J. Spencer. Asymptotically Good Coverings. Pacific Journal of Mathematics, 118(2):575–586, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dubhashi, D., Panconesi, A. (1995). Near-optimal distributed edge coloring. In: Spirakis, P. (eds) Algorithms — ESA '95. ESA 1995. Lecture Notes in Computer Science, vol 979. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60313-1_162
Download citation
DOI: https://doi.org/10.1007/3-540-60313-1_162
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60313-9
Online ISBN: 978-3-540-44913-3
eBook Packages: Springer Book Archive