Publications with Kshitij Jain
- Reconfiguring undirected paths.
E. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara, and Y. Uno.
arXiv:1905.00518.
16th Algorithms and Data Structures Symp. (WADS 2019), Edmonton, Alberta.
Springer, Lecture Notes in Comp. Sci. 11646 (2019), pp. 353–365.
A motion that slides an undirected path along its length from one configuration to another in a graph (allowing moves in both directions) can be found in time that is fixed-parameter tractable in the path length. However the problem is PSPACE-complete for paths of unbounded length, even when the host graph has bounded bandwidth.
(Slides)
- Face flips in origami tessellations.
H. A. Akitaya, V. Dujmović, D. Eppstein, T. Hull, K. Jain, and A. Lubiw.
arXiv:1910.05667.
J. Computational Geometry 11 (1): 397–417, 2020.We study problems in which we are given an origami crease pattern and seek to reconfigure one locally flat foldable mountain-valley assignment into another by a sequence of operations that change the assignment around a single face of the crease pattern.