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