Speaker: |
Anamay Tengse |

Organiser: |
Gunjan Kumar |

Date: |
Friday, 30 Sep 2016, 16:00 to 17:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In this talk we will see an algorithm to optimally color the given path, that runs in time $O(n + S(n))$, where $n$ is the number of vertices and $S(n)$ is the time required to sort the vertex weights. We will then proceed to see a proof of a lower bound matching this running time.

This result appears in ISAAC 2009, titled `Max-coloring paths: Tight bounds and extensions' by Kavitha Telikepalli and Juli\'an Mestre.