Главная
Study mode:
on
1
Reconfiguring Simple st Hamiltonian Paths in Rectangular Grid Graphs
2
In this paper...
3
Rectangular Grid Graph G
4
An s,t Hamiltonian path
5
Reconfiguration......
6
Related work: Reconfiguring Hamiltonian cycles in grid graphs
7
Why study the problem
8
Reconfiguring simple paths
9
Operation: Pairs of Switches
10
A simple s,t Hamiltonian path
11
Structure of simple path: the regions
12
Mechanism to pair switches: Zip
13
The algorithm...
14
P to Canonical path: an example
15
Canonical to canonical path
16
Simple to Canonical: other scenarios
17
Summary of our contribution
18
Open problems...
Description:
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

Fields Institute
Add to list
#Mathematics #Graph Theory #Computer Science #Algorithms #Combinatorial Algorithms
1 of 18

Reconfiguring Simple st Hamiltonian Paths in Rectangular Grid Graphs