LIPIcs, Volume 100
FUN 2018, June 13-15, 2018, La Maddalena, Italy
Editors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Proceedings{ito_et_al:LIPIcs.FUN.2018, title = {{LIPIcs, Volume 100, FUN'18, Complete Volume}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, 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}, URN = {urn:nbn:de:0030-drops-89311}, doi = {10.4230/LIPIcs.FUN.2018}, annote = {Keywords: Theory of computation, Complexity classes, Algorithm design techniques, Computability, Approximation algorithms analysis, Mathematics of computing} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ito_et_al:LIPIcs.FUN.2018.0, author = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {0:i--0:xi}, 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.0}, URN = {urn:nbn:de:0030-drops-87914}, doi = {10.4230/LIPIcs.FUN.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Martín Farach-Colton. Mind the Gap (Invited Paper). In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{farachcolton:LIPIcs.FUN.2018.1, author = {Farach-Colton, Mart{\'\i}n}, title = {{Mind the Gap}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-87924}, doi = {10.4230/LIPIcs.FUN.2018.1}, annote = {Keywords: library sort, Italian island, packed memory arrays, weight balanced trees, Italians know how to throw a conference} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Kokichi Sugihara. Evolution of Impossible Objects (Invited Paper). In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 2:1-2:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{sugihara:LIPIcs.FUN.2018.2, author = {Sugihara, Kokichi}, title = {{Evolution of Impossible Objects}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {2:1--2:8}, 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.2}, URN = {urn:nbn:de:0030-drops-87939}, doi = {10.4230/LIPIcs.FUN.2018.2}, annote = {Keywords: Ambiguous cylinder, anomalous picture, impossible motion, impossible object, optical illusion} }
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)
Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Tracks from hell - when finding a proof may be easier than checking it. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{almanza_et_al:LIPIcs.FUN.2018.4, author = {Almanza, Matteo and Leucci, Stefano and Panconesi, Alessandro}, title = {{Tracks from hell - when finding a proof may be easier than checking it}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {4:1--4:13}, 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.4}, URN = {urn:nbn:de:0030-drops-87954}, doi = {10.4230/LIPIcs.FUN.2018.4}, annote = {Keywords: puzzle games, solitaire games, Trainyard, verification} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi. How Bad is the Freedom to Flood-It?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{belmonte_et_al:LIPIcs.FUN.2018.5, author = {Belmonte, R\'{e}my and Khosravian Ghadikolaei, Mehdi and Kiyomi, Masashi and Lampis, Michael and Otachi, Yota}, title = {{How Bad is the Freedom to Flood-It?}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {5:1--5:13}, 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.5}, URN = {urn:nbn:de:0030-drops-87961}, doi = {10.4230/LIPIcs.FUN.2018.5}, annote = {Keywords: flood-filling game, parameterized complexity} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bermond_et_al:LIPIcs.FUN.2018.6, author = {Bermond, Jean-Claude and Chaintreau, Augustin and Ducoffe, Guillaume and Mazauric, Dorian}, title = {{How long does it take for all users in a social network to choose their communities?}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {6:1--6: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.6}, URN = {urn:nbn:de:0030-drops-87972}, doi = {10.4230/LIPIcs.FUN.2018.6}, annote = {Keywords: communities, social networks, integer partitions, coloring games, graphs} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Davide Bilò, Luciano Gualà, Stefano Leucci, and Neeldhara Misra. On the Complexity of Two Dots for Narrow Boards and Few Colors. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bilo_et_al:LIPIcs.FUN.2018.7, author = {Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Misra, Neeldhara}, title = {{On the Complexity of Two Dots for Narrow Boards and Few Colors}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {7:1--7:15}, 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.7}, URN = {urn:nbn:de:0030-drops-87988}, doi = {10.4230/LIPIcs.FUN.2018.7}, annote = {Keywords: puzzle, NP-complete, perfect information, combinatorial game theory} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bilo_et_al:LIPIcs.FUN.2018.8, author = {Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko}, title = {{On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {8:1--8:15}, 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.8}, URN = {urn:nbn:de:0030-drops-87994}, doi = {10.4230/LIPIcs.FUN.2018.8}, annote = {Keywords: peg duotaire, pspace-completeness, peg solitaire, two-player games} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Hans L. Bodlaender and Tom C. van der Zanden. On the Exact Complexity of Polyomino Packing. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bodlaender_et_al:LIPIcs.FUN.2018.9, author = {Bodlaender, Hans L. and van der Zanden, Tom C.}, title = {{On the Exact Complexity of Polyomino Packing}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {9:1--9:10}, 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.9}, URN = {urn:nbn:de:0030-drops-88001}, doi = {10.4230/LIPIcs.FUN.2018.9}, annote = {Keywords: polyomino packing, exact complexity, exponential time hypothesis} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Paolo Boldi and Sebastiano Vigna. Kings, Name Days, Lazy Servants and Magic. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{boldi_et_al:LIPIcs.FUN.2018.10, author = {Boldi, Paolo and Vigna, Sebastiano}, title = {{Kings, Name Days, Lazy Servants and Magic}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {10:1--10:13}, 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.10}, URN = {urn:nbn:de:0030-drops-88017}, doi = {10.4230/LIPIcs.FUN.2018.10}, annote = {Keywords: Suffix trees, suffix arrays, z-fast tries, prefix search} }
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)
Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, and Andreas Tönnis. SUPERSET: A (Super)Natural Variant of the Card Game SET. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{botler_et_al:LIPIcs.FUN.2018.12, author = {Botler, F\'{a}bio and Cristi, Andr\'{e}s and Hoeksma, Ruben and Schewior, Kevin and T\"{o}nnis, Andreas}, title = {{SUPERSET: A (Super)Natural Variant of the Card Game SET}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {12:1--12:17}, 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.12}, URN = {urn:nbn:de:0030-drops-88035}, doi = {10.4230/LIPIcs.FUN.2018.12}, annote = {Keywords: SET, SUPERSET, card game, cap set, affine geometry, computational complexity} }
Feedback for Dagstuhl Publishing