Explore the reconfiguration of simple s,t Hamiltonian paths in rectangular grid graphs in this 22-minute conference talk from IWOCA 2021. Delve into the structure of simple paths, the mechanism of pairing switches using the "Zip" technique, and the algorithm for transforming paths. Examine various scenarios, including the transformation from simple to canonical paths, and understand the contributions made to this field of study. Conclude by considering open problems and future research directions in the reconfiguration of Hamiltonian paths in grid graphs.
Reconfiguring Simple ST Hamiltonian Paths in Rectangular Grid Graphs
Overview
Syllabus
Reconfiguring Simple st Hamiltonian Paths in Rectangular Grid Graphs
In this paper...
Rectangular Grid Graph G
An s,t Hamiltonian path
Reconfiguration......
Related work: Reconfiguring Hamiltonian cycles in grid graphs
Why study the problem
Reconfiguring simple paths
Operation: Pairs of Switches
A simple s,t Hamiltonian path
Structure of simple path: the regions
Mechanism to pair switches: Zip
The algorithm...
P to Canonical path: an example
Canonical to canonical path
Simple to Canonical: other scenarios
Summary of our contribution
Open problems...
Taught by
Fields Institute
