Campus Event Calendar
Event Entry
What and Who
Subcoloring Interval Graphs
Rajiv Raman
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 22 May 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Given a graph G=(V,E), the subcoloring problem asks for the partition
of the vertex set of G into the fewest number of sets V_1,...V_k
such that each V_i is a union of disjoint cliques. The subchromatic number of a graph is the smallest k for which such a partition exists.
The subcoloring of a graph is a generalization of the classic coloring
problem, where each V_i can be seen as a union of disjoint cliques of size 1. In this talk I will present an approximation algorithm for subcoloring of interval graphs, and give applications of subcolorings.
Contact
Rajiv Raman
+49 681 9325 115
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Approximation Algorithms, Graph Coloring
Rajiv Raman, 05/14/2009 17:05 -- Created document.