BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/715
DTSTAMP:20230914T125935Z
SUMMARY:Max-coloring Paths
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nThe max-coloring problem 
 is to compute a legal coloring of the vertices of a graph $G=(V\,E)$ with 
 vertex weights $w$ such that $sum^k_{i=1} max_{v \\in C_i} w(v_i)$ is mini
 mized\, where $C_1\, \\ldots \,C_k$ are the various color classes. For gen
 eral graphs\, max-coloring is as hard as the classical vertex coloring pro
 blem. Here we study the max-coloring problem for simple paths. Note that i
 f the vertices are unweighted\, this reduces to the classical vertex color
 ing problem and hence the solution is to use 2 colors. However for the wei
 ghted case\, one can construct simple instances where using more colors tu
 rns out to be optimal.\n\nIn this talk we will see an algorithm to optimal
 ly color the given path\, that runs in time $O(n + S(n))$\, where $n$ is t
 he number of vertices and $S(n)$ is the time required to sort the vertex w
 eights. We will then proceed to see a proof of a lower bound matching this
  running time.\n\nThis result appears in ISAAC 2009\, titled `Max-coloring
  paths: Tight bounds and extensions' by Kavitha Telikepalli and Juli\\'an 
 Mestre.\n
URL:https://www.tcs.tifr.res.in/web/events/715
DTSTART;TZID=Asia/Kolkata:20160930T160000
DTEND;TZID=Asia/Kolkata:20160930T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR