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.
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.
Seminar Location: The seminars are held at:
    Virginia Tech, Corporate Research Center
    1880 Pratt Drive, Building XV
    Seminar Room 2018, Second Floor
    Directions: Map (PDF)

Back to: NDSSL Seminar Page

Copyright Virginia Bioinformatics Institute © 2005