School of Technology and Computer Science Seminars
Alternation-free Sequences and Parametric Shortest Paths
by Kshitij Gajjar (STCS, TIFR)
Friday, January 25, 2019
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
Abstract: In this talk, we will see a close connection between alternation-free sequences of words over the alphabet $\mathbb{Z}_n$ and parametric shortest paths in certain graphs. Turns out, in the case of planar graphs, these are words over the alphabet $\mathbb{Z}_2$. Also, as an application of alternation-free sequences, we will see that thin grid graphs have small parametric complexity. This shows a dichotomy between thin grids and square grids, as square grids have large parametric complexity. This is based on joint work with Prof. J. Radhakrishnan. |
Organised by | Sayantan Chakraborty |