Document Type
Technical Report
Publication Date
2015-8
Technical Report Number
WUCSE-2015-002
Abstract
This paper introduces a natural generalization of the classical edge coloring problem in graphs that provides a useful abstraction for two well-known problems in multicast switching. We show that the problem is NP-hard and evaluate the performance of several approximation algorithms, both analytically and experimentally. We find that for random χ-colorable graphs, the number of colors used by the best algorithms falls within a small constant factor of χ, where the constant factor is mainly a function of the ratio of the number of outputs to inputs. When this ratio is less than 10, the best algorithms produces solutions that use fewer than 2χ colors. In addition, one of the algorithms studied finds high quality approximate solutions for any graph with high probability, where the probability of a low quality solution is a function only of the random choices made by the algorithm.
Recommended Citation
Turner, Jonathan, "The Edge Group Coloring Problem with Applications to Multicast Switching" Report Number: WUCSE-2015-002 (2015). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/243
Comments
Permanent URL: http://dx.doi.org/10.7936/K7707ZPM