Paper by Erik D. Demaine
- Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, and Jayson Lynch, “Traversability, Reconfiguration, and Reachability in the Gadget Framework”, in Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), edited by Petra Mutzel, Md. Saidur Rahman, and Slamin, Lecture Notes in Computer Science, volume 13174, Jember, Indonesia, March 2022, pages 47–58.
Consider an agent traversing a graph of “gadgets”, each with local
state that changes with each traversal by the agent. Prior work has studied
the computational complexity of deciding whether the agent can reach a target
location given a graph containing many copies of a given type of gadget. This
paper introduces new goals and studies examples where the computational
complexity of these problems are the same or differ from the original
relocation goal. For several classes of gadgets—DAG gadgets, one-state
gadgets, and reversible deterministic gadgets—we give a partial
characterization of their complexity when the goal is to traverse every gadget
at least once. We also study the complexity of reconfiguration, where the
goal is to bring the entire system of gadgets to a specified state. We give
examples where reconfiguration is a strictly harder problem than relocating
the agent, and also examples where relocation is strictly harder. We also give
a partial characterization of the complexity of reconfiguration with
reversible deterministic gadgets.
- This paper is also available as arXiv:2204.00600 and from SpringerLink.
- The paper is available in PDF (412k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- GadgetsVictory_Algorithmica (Traversability, Reconfiguration, and Reachability in the Gadget Framework)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by