Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. Hardness of Token Swapping on Trees. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aichholzer_et_al:LIPIcs.ESA.2022.3, author = {Aichholzer, Oswin and Demaine, Erik D. and Korman, Matias and Lubiw, Anna and Lynch, Jayson and Mas\'{a}rov\'{a}, Zuzana and Rudoy, Mikhail and Vassilevska Williams, Virginia and Wein, Nicole}, title = {{Hardness of Token Swapping on Trees}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.3}, URN = {urn:nbn:de:0030-drops-169413}, doi = {10.4230/LIPIcs.ESA.2022.3}, annote = {Keywords: Sorting, Token swapping, Trees, NP-hard, Approximation} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7, author = {Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi}, title = {{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7}, URN = {urn:nbn:de:0030-drops-127681}, doi = {10.4230/LIPIcs.FUN.2021.7}, annote = {Keywords: puzzles, sliding blocks, PSPACE-hardness} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{akitaya_et_al:LIPIcs.SoCG.2019.9, author = {Akitaya, Hugo A. and Korman, Matias and Rudoy, Mikhail and Souvaine, Diane L. and T\'{o}th, Csaba D.}, title = {{Circumscribing Polygons and Polygonizations for Disjoint Line Segments}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.9}, URN = {urn:nbn:de:0030-drops-104136}, doi = {10.4230/LIPIcs.SoCG.2019.9}, annote = {Keywords: circumscribing polygon, Hamiltonicity, extremal combinatorics} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{abel_et_al:LIPIcs.FUN.2018.3, author = {Abel, Zachary and Bosboom, Jeffrey and Demaine, Erik D. and Hamilton, Linus and Hesterberg, Adam and Kopinsky, Justin and Lynch, Jayson and Rudoy, Mikhail}, title = {{Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {3:1--3:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.3}, URN = {urn:nbn:de:0030-drops-87944}, doi = {10.4230/LIPIcs.FUN.2018.3}, annote = {Keywords: video games, puzzles, hardness} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Jeffrey Bosboom, Erik D. Demaine, and Mikhail Rudoy. Computational Complexity of Generalized Push Fight. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bosboom_et_al:LIPIcs.FUN.2018.11, author = {Bosboom, Jeffrey and Demaine, Erik D. and Rudoy, Mikhail}, title = {{Computational Complexity of Generalized Push Fight}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {11:1--11:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.11}, URN = {urn:nbn:de:0030-drops-88029}, doi = {10.4230/LIPIcs.FUN.2018.11}, annote = {Keywords: board games, hardness, mate-in-one} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy. Computational Complexity of Motion Planning of a Robot through Simple Gadgets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.FUN.2018.18, author = {Demaine, Erik D. and Grosof, Isaac and Lynch, Jayson and Rudoy, Mikhail}, title = {{Computational Complexity of Motion Planning of a Robot through Simple Gadgets}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {18:1--18:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.18}, URN = {urn:nbn:de:0030-drops-88098}, doi = {10.4230/LIPIcs.FUN.2018.18}, annote = {Keywords: PSPACE, hardness, motion planning, puzzles} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Erik D. Demaine and Mikhail Rudoy. Tree-Residue Vertex-Breaking: a new tool for proving hardness. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.SWAT.2018.32, author = {Demaine, Erik D. and Rudoy, Mikhail}, title = {{Tree-Residue Vertex-Breaking: a new tool for proving hardness}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.32}, URN = {urn:nbn:de:0030-drops-88586}, doi = {10.4230/LIPIcs.SWAT.2018.32}, annote = {Keywords: NP-hardness, graphs, Hamiltonicity, hypergraph spanning tree} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Erik D. Demaine, Sarah Eisenstat, and Mikhail Rudoy. Solving the Rubik's Cube Optimally is NP-complete. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.STACS.2018.24, author = {Demaine, Erik D. and Eisenstat, Sarah and Rudoy, Mikhail}, title = {{Solving the Rubik's Cube Optimally is NP-complete}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {24:1--24:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.24}, URN = {urn:nbn:de:0030-drops-85336}, doi = {10.4230/LIPIcs.STACS.2018.24}, annote = {Keywords: combinatorial puzzles, NP-hardness, group theory, Hamiltonicity} }
Feedback for Dagstuhl Publishing