LIPIcs, Volume 226
FUN 2022, May 30 to June 3, 2022, Island of Favignana, Sicily, Italy
Editors: Pierre Fraigniaud and Yushi Uno
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1-450, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{fraigniaud_et_al:LIPIcs.FUN.2022, title = {{LIPIcs, Volume 226, FUN 2022, Complete Volume}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {1--450}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022}, URN = {urn:nbn:de:0030-drops-159693}, doi = {10.4230/LIPIcs.FUN.2022}, annote = {Keywords: LIPIcs, Volume 226, FUN 2022, Complete Volume} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fraigniaud_et_al:LIPIcs.FUN.2022.0, author = {Fraigniaud, Pierre and Uno, Yushi}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {0:i--0:xii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.0}, URN = {urn:nbn:de:0030-drops-159703}, doi = {10.4230/LIPIcs.FUN.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta. Pushing Blocks by Sweeping Lines. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1, author = {A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni}, title = {{Pushing Blocks by Sweeping Lines}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {1:1--1:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.1}, URN = {urn:nbn:de:0030-drops-159719}, doi = {10.4230/LIPIcs.FUN.2022.1}, annote = {Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Miguel Ambrona. A Practical Algorithm for Chess Unwinnability. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ambrona:LIPIcs.FUN.2022.2, author = {Ambrona, Miguel}, title = {{A Practical Algorithm for Chess Unwinnability}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {2:1--2:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.2}, URN = {urn:nbn:de:0030-drops-159721}, doi = {10.4230/LIPIcs.FUN.2022.2}, annote = {Keywords: chess, helpmate, unwinnability, timeout, dead position} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 3:1-3:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ani_et_al:LIPIcs.FUN.2022.3, author = {Ani, Joshua and Chung, Lily and Demaine, Erik D. and Diomidov, Yevhenii and Hendrickson, Dylan and Lynch, Jayson}, title = {{Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {3:1--3:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.3}, URN = {urn:nbn:de:0030-drops-159737}, doi = {10.4230/LIPIcs.FUN.2022.3}, annote = {Keywords: gadgets, motion planning, hardness of games} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Marcella Anselmo, Manuela Flores, and Maria Madonia. Fun Slot Machines and Transformations of Words Avoiding Factors. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{anselmo_et_al:LIPIcs.FUN.2022.4, author = {Anselmo, Marcella and Flores, Manuela and Madonia, Maria}, title = {{Fun Slot Machines and Transformations of Words Avoiding Factors}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.4}, URN = {urn:nbn:de:0030-drops-159743}, doi = {10.4230/LIPIcs.FUN.2022.4}, annote = {Keywords: Isometric words, Words avoiding factors, Index of a word, Overlap, Lee distance} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
N.R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess Is Hard Even for a Single Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aravind_et_al:LIPIcs.FUN.2022.5, author = {Aravind, N.R. and Misra, Neeldhara and Mittal, Harshil}, title = {{Chess Is Hard Even for a Single Player}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.5}, URN = {urn:nbn:de:0030-drops-159753}, doi = {10.4230/LIPIcs.FUN.2022.5}, annote = {Keywords: chess, strategy, board games, NP-complete} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Rolling Polyhedra on Tessellations. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{baes_et_al:LIPIcs.FUN.2022.6, author = {Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron}, title = {{Rolling Polyhedra on Tessellations}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6}, URN = {urn:nbn:de:0030-drops-159761}, doi = {10.4230/LIPIcs.FUN.2022.6}, annote = {Keywords: polyhedra, tilings} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bramas_et_al:LIPIcs.FUN.2022.7, author = {Bramas, Quentin and Devismes, St\'{e}phane and Durand, Ana\"{i}s and Lafourcade, Pascal and Lamani, Anissa}, title = {{Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.7}, URN = {urn:nbn:de:0030-drops-159771}, doi = {10.4230/LIPIcs.FUN.2022.7}, annote = {Keywords: Bee extinction, luminous swarms of beedroids, perpetual flower pollination problem, greenhouse} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Gerth Stølting Brodal. Priority Queues with Decreasing Keys. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{brodal:LIPIcs.FUN.2022.8, author = {Brodal, Gerth St{\o}lting}, title = {{Priority Queues with Decreasing Keys}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {8:1--8:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.8}, URN = {urn:nbn:de:0030-drops-159787}, doi = {10.4230/LIPIcs.FUN.2022.8}, annote = {Keywords: priority queue, decreasing keys, post-order heap, Dijkstra’s algorithm} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Xavier Bultel. Zero-Knowledge Proof of Knowledge for Peg Solitaire. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bultel:LIPIcs.FUN.2022.9, author = {Bultel, Xavier}, title = {{Zero-Knowledge Proof of Knowledge for Peg Solitaire}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.9}, URN = {urn:nbn:de:0030-drops-159798}, doi = {10.4230/LIPIcs.FUN.2022.9}, annote = {Keywords: Zero-Knowledge Proof, Peg Solitaire} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{burke_et_al:LIPIcs.FUN.2022.10, author = {Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua}, title = {{Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.10}, URN = {urn:nbn:de:0030-drops-159808}, doi = {10.4230/LIPIcs.FUN.2022.10}, annote = {Keywords: Combinatorial Games, Nim, Generalized Geography, Sprague-Grundy Theory, Grundy value, Computational Complexity, Functional-Preserving Reductions} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{burke_et_al:LIPIcs.FUN.2022.11, author = {Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua}, title = {{Quantum-Inspired Combinatorial Games: Algorithms and Complexity}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.11}, URN = {urn:nbn:de:0030-drops-159812}, doi = {10.4230/LIPIcs.FUN.2022.11}, annote = {Keywords: Quantum-Inspired Games, Combinatorial Games, Computational Complexity, Polynomial Hierarchy, \c{c}lass\{PSPACE\}, Nim, Generalized Geography, Snort} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bermond_et_al:LIPIcs.FUN.2022.12, author = {Bermond, Jean-Claude and Havet, Fr\'{e}d\'{e}ric and Cosnard, Michel}, title = {{Grabbing Olives on Linear Pizzas and Pissaladi\`{e}res}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.12}, URN = {urn:nbn:de:0030-drops-159826}, doi = {10.4230/LIPIcs.FUN.2022.12}, annote = {Keywords: Grabbing game, degenerate graph, path, grid} }
Feedback for Dagstuhl Publishing