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 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Avinandan Das, Pierre Fraigniaud, and Adi Rosén. Distributed Partial Coloring via Gradual Rounding. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{das_et_al:LIPIcs.OPODIS.2023.30, author = {Das, Avinandan and Fraigniaud, Pierre and Ros\'{e}n, Adi}, title = {{Distributed Partial Coloring via Gradual Rounding}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {30:1--30:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.30}, URN = {urn:nbn:de:0030-drops-195205}, doi = {10.4230/LIPIcs.OPODIS.2023.30}, annote = {Keywords: Distributed graph coloring, partial coloring, weak coloring} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{attiya_et_al:LIPIcs.DISC.2023.4, author = {Attiya, Hagit and Fraigniaud, Pierre and Paz, Ami and Rajsbaum, Sergio}, title = {{One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.4}, URN = {urn:nbn:de:0030-drops-191304}, doi = {10.4230/LIPIcs.DISC.2023.4}, annote = {Keywords: Wait-free computing, lower bounds} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Romain Cosson, Laurent Massoulié, and Laurent Viennot. Efficient Collaborative Tree Exploration with Breadth-First Depth-Next. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cosson_et_al:LIPIcs.DISC.2023.14, author = {Cosson, Romain and Massouli\'{e}, Laurent and Viennot, Laurent}, title = {{Efficient Collaborative Tree Exploration with Breadth-First Depth-Next}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {14:1--14:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.14}, URN = {urn:nbn:de:0030-drops-191409}, doi = {10.4230/LIPIcs.DISC.2023.14}, annote = {Keywords: collaborative exploration, online algorithms, trees, adversarial game, competitive analysis, robot swarms} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed Certification for Classes of Dense Graphs. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2023.20, author = {Fraigniaud, Pierre and Mazoit, Fr\'{e}d\'{e}ric and Montealegre, Pedro and Rapaport, Ivan and Todinca, Ioan}, title = {{Distributed Certification for Classes of Dense Graphs}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.20}, URN = {urn:nbn:de:0030-drops-191467}, doi = {10.4230/LIPIcs.DISC.2023.20}, annote = {Keywords: CONGEST, Proof Labelling Schemes, clique-width, MSO} }
Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Computing Power of Hybrid Models in Synchronous Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fraigniaud_et_al:LIPIcs.OPODIS.2022.20, author = {Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan}, title = {{Computing Power of Hybrid Models in Synchronous Networks}}, booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)}, pages = {20:1--20:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-265-5}, ISSN = {1868-8969}, year = {2023}, volume = {253}, editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.20}, URN = {urn:nbn:de:0030-drops-176401}, doi = {10.4230/LIPIcs.OPODIS.2022.20}, annote = {Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie. Fault Tolerant Coloring of the Asynchronous Cycle. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.23, author = {Fraigniaud, Pierre and Lambein-Monette, Patrick and Rabie, Mika\"{e}l}, title = {{Fault Tolerant Coloring of the Asynchronous Cycle}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {23:1--23:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.23}, URN = {urn:nbn:de:0030-drops-172147}, doi = {10.4230/LIPIcs.DISC.2022.23}, annote = {Keywords: graph coloring, LOCAL model, shared-memory model, immediate snapshot, renaming, wait-free algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.43, author = {Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan}, title = {{Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {43:1--43:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.43}, URN = {urn:nbn:de:0030-drops-172345}, doi = {10.4230/LIPIcs.DISC.2022.43}, annote = {Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique} }
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} }
Feedback for Dagstuhl Publishing