Complexity Science Seminar Series - Abstracts
Title: Chromatic Scheduling Problems
Presenter: Rajiv Raman
Dept. of Computer Science, University of Iowa
Date and Time: Monday, April 02, 2007, 3:00-4:00 PM
Abstract:
Several resource allocation and scheduling problems can be modeled naturally as coloring problems on graphs. A classic example is the scheduling of traffic lights at an intersection, or allocating time-slots for communication in a network.Seminar Location: The seminars are held at:
We present some graph coloring problems that are motivated by scheduling and resource allocation applications. Specifically, we present results on the "max-coloring problem" that models the scheduling of conflicting jobs in batches. We present approximation algorithms for various classes of graphs.
Virginia Tech, Corporate Research Center
1880 Pratt Drive, Building XV
Seminar Room 2018, Second Floor
Directions: Map (PDF)
Back to: NDSSL Seminar Page