Tata Institute of Fundamental Research
Alternation-free Sequences and Parametric Shortest Paths
STCS Student Seminar
Speaker:
Kshitij Gajjar
Organiser:
Sayantan Chakraborty
Date:
Friday, 25 Jan 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Kshitij Gajjar |
| Organiser: | Sayantan Chakraborty |
| Date: | Friday, 25 Jan 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.