Structural Information and Communication Complexity: 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29–July 1, 2020, Proceedings (Lecture Notes in Computer Science Book 12156)

This book constitutes the refereed conference proceedings of the 27th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2020, held in Paderborn, Germany, in June 2020.\* The 19 full papers and 2 invited papers presented in this book were carefully reviewed and selected from 41 submissions. They are divided into seven sections, i.e. invited papers; mobile robots; dynamic graphs; network communication; multi-agent systems; communication complexity; and game theory. **\*** The conference was held virtually due to the COVID-19 pandemic. Front Matter ....Pages i-xii Front Matter ....Pages 1-1 Network Decomposition and Distributed Derandomization (Invited Paper) (Mohsen Ghaffari)....Pages 3-18 Resource Burning for Permissionless Systems (Invited Paper) (Diksha Gupta, Jared Saia, Maxwell Young)....Pages 19-44 Front Matter ....Pages 45-45 ANTS on a Plane (Abhinav Aggarwal, Jared Saia)....Pages 47-62 Local Gathering of Mobile Robots in Three Dimensions (Michael Braun, Jannik Castenow, Friedhelm Meyer auf der Heide)....Pages 63-79 Improved Lower Bounds for Shoreline Search (Stefan Dobrev, Rastislav Královič, Dana Pardubská)....Pages 80-90 Guarding a Polygon Without Losing Touch (Barath Ashok, John Augustine, Aditya Mehekare, Sridhar Ragupathi, Srikkanth Ramachandran, Suman Sourav)....Pages 91-108 Front Matter ....Pages 109-109 Random Walks on Randomly Evolving Graphs (Leran Cai, Thomas Sauerwald, Luca Zanetti)....Pages 111-128 Non-strict Temporal Exploration (Thomas Erlebach, Jakob T. Spooner)....Pages 129-145 Exploration of Time-Varying Connected Graphs with Silent Agents (Stefan Dobrev, Rastislav Královič, Dana Pardubská)....Pages 146-162 Front Matter ....Pages 163-163 Optimal Packet-Oblivious Stable Routing in Multi-hop Wireless Networks (Vicent Cholvi, Paweł Garncarek, Tomasz Jurdziński, Dariusz R. Kowalski)....Pages 165-182 Stateless Information Dissemination Algorithms (Volker Turau)....Pages 183-199 Front Matter ....Pages 201-201 Cops and Robbers on Dynamic Graphs: Offline and Online Case (Stefan Balev, Juan Luis Laredo Jiménez, Ioannis Lamprou, Yoann Pigné, Eric Sanlaville)....Pages 203-219 Black Virus Decontamination of Synchronous Ring Networks by Initially Scattered Mobile Agents (Nikos Giachoudis, Maria Kokkou, Euripides Markou)....Pages 220-236 The Power of Global Knowledge on Self-stabilizing Population Protocols (Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, Toshimitsu Masuzawa)....Pages 237-254 Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions (Francesco d’Amore, Andrea Clementi, Emanuele Natale)....Pages 255-272 Front Matter ....Pages 273-273 Distributed Testing of Distance-k Colorings (Pierre Fraigniaud, Magnús M. Halldórsson, Alexandre Nolin)....Pages 275-290 Communication Complexity of Wait-Free Computability in Dynamic Networks (Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum)....Pages 291-309 Distance Labeling Schemes for \(K_4\)-Free Bridged Graphs (Victor Chepoi, Arnaud Labourel, Sébastien Ratel)....Pages 310-327 Front Matter ....Pages 329-329 Multi-winner Election Control via Social Influence (M. Abouei Mehrizi, Gianlorenzo D’Angelo)....Pages 331-348 Network Creation Games with Local Information and Edge Swaps (Shotaro Yoshimura, Yukiko Yamauchi)....Pages 349-365 The Value of Information in Selfish Routing (Simon Scherrer, Adrian Perrig, Stefan Schmid)....Pages 366-384 Back Matter ....Pages 385-385