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

Comments

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

Download

Share

COinS