Title

The Bounded Edge Coloring Problem and Offline Crossbar Scheduling

Authors

Jonathan Turner, Washington University in St LouisFollow

Document Type

Technical Report

Publication Date

2015-12

Filename

WUCSE-2015-007.pdf

DOI:

10.7936/K7R20ZP9

Technical Report Number

WUCSE-2015-007

Abstract

This paper introduces a variant of the classical edge coloring problem in graphs that can be applied to an offline scheduling problem for crossbar switches. We show that the problem is NP-complete, develop three lower bounds bounds on the optimal solution value and evaluate the performance of several approximation algorithms, both analytically and experimentally. We show how to approximate an optimal solution with a worst-case performance ratio of 3/2 and our experimental results demonstrate that the best algorithms produce results that very closely track a lower bound.

Comments

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

Recommended Citation

Turner, Jonathan, "The Bounded Edge Coloring Problem and Offline Crossbar Scheduling" Report Number: WUCSE-2015-007 (2015). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/510