G²OAT seminar: Reconfiguration Using Generalized Token Jumping


6. 5. 2024
13:00 – 14:00


Room TH:A-1247

Thákurova 7, Prague 6



Jan Matyáš Křišťan (FIT CTU) will speak at the regular Monday seminar of the G²OAT group. In his talk, he will discuss reconfiguration in graphical problems, where he will focus on the possibilities of transition between two solutions using small steps, both by moving one token to any vertex of the graph (Token Jumping) and by moving a token to an adjacent vertex (Token Sliding).

Event website


Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. We study the effect of permutation pattern-avoidance on the complexity of optimization problems.

In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC 1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015) conjectured that the amortized search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding

More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures.

The person responsible for the content of this page: Bc. Veronika Dvořáková