## All Computer Science and Engineering Research

Technical Report

#### Department

Computer Science and Engineering

2015-8

#### Filename

WUCSE-2015-002.pdf

10.7936/K7707ZPM

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 {\sl NP}-hard and evaluate the performance of several approximation algorithms, both analytically and experimentally. We find that for random $\chi$-colorable graphs, the number of colors used by the best algorithms falls within a small constant factor of $\chi$, 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\chi$ 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.