Near-Optimal Distributed Edge Coloring

Devdatt P. Dubhashi, Alessandro Panconesi

Abstract

We give a distributed randomized algorithm to edge color a network. Given a graph G with n nodes and maximum degree Δ, the algorithm,
BibTeX
@inproceedings{dubhashi1995near,
  author = {Devdatt P. Dubhashi and Alessandro Panconesi},
  title = {{Near-Optimal Distributed Edge Coloring}},
  booktitle = {ESA},
  year = {1995},
  doi = {10.1007/3-540-60313-1\_162},
}

Loading related content...

Figure