Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2015-8

Filename

WUCSE-2015-002.pdf

DOI:

10.7936/K7707ZPM

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 {\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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7707ZPM

Share

COinS