Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Nina Klobas, George B. Mertzios, and Paul G. Spirakis. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 5:1-5:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{klobas_et_al:LIPIcs.MFCS.2023.5, author = {Klobas, Nina and Mertzios, George B. and Spirakis, Paul G.}, title = {{Sliding into the Future: Investigating Sliding Windows in Temporal Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {5:1--5:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.5}, URN = {urn:nbn:de:0030-drops-185397}, doi = {10.4230/LIPIcs.MFCS.2023.5}, annote = {Keywords: Temporal Graphs, Sliding Time Windows} }
Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Allen Ibiapina and Ana Silva. Snapshot Disjointness in Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1:1-1:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ibiapina_et_al:LIPIcs.SAND.2023.1, author = {Ibiapina, Allen and Silva, Ana}, title = {{Snapshot Disjointness in Temporal Graphs}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {1:1--1:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.1}, URN = {urn:nbn:de:0030-drops-179379}, doi = {10.4230/LIPIcs.SAND.2023.1}, annote = {Keywords: Temporal graphs, Menger’s Theorem, Snapshot disjointness} }
Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial Gathering of Mobile Agents in Dynamic Tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 2:1-2:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{shibata_et_al:LIPIcs.SAND.2023.2, author = {Shibata, Masahiro and Kitamura, Naoki and Eguchi, Ryota and Sudo, Yuichi and Nakamura, Junya and Kim, Yonghwan}, title = {{Partial Gathering of Mobile Agents in Dynamic Tori}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {2:1--2:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.2}, URN = {urn:nbn:de:0030-drops-179387}, doi = {10.4230/LIPIcs.SAND.2023.2}, annote = {Keywords: distributed system, mobile agents, partial gathering, dynamic tori} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Leszek Gąsieniec, Paul G. Spirakis, and Grzegorz Stachowiak. New Clocks, Optimal Line Formation and Self-Replication Population Protocols. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 33:1-33:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{gasieniec_et_al:LIPIcs.STACS.2023.33, author = {G\k{a}sieniec, Leszek and Spirakis, Paul G. and Stachowiak, Grzegorz}, title = {{New Clocks, Optimal Line Formation and Self-Replication Population Protocols}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {33:1--33:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.33}, URN = {urn:nbn:de:0030-drops-176857}, doi = {10.4230/LIPIcs.STACS.2023.33}, annote = {Keywords: Population protocols, constructors, probabilistic bubble-sort, self-replication} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Leszek Gąsieniec, Paul Spirakis, and Grzegorz Stachowiak. Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 44:1-44:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gasieniec_et_al:LIPIcs.DISC.2022.44, author = {G\k{a}sieniec, Leszek and Spirakis, Paul and Stachowiak, Grzegorz}, title = {{Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {44:1--44: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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.44}, URN = {urn:nbn:de:0030-drops-172351}, doi = {10.4230/LIPIcs.DISC.2022.44}, annote = {Keywords: Population protocols, network constructors, probabilistic bubble-sort, self-replication} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss. Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{amram_et_al:LIPIcs.DISC.2022.5, author = {Amram, Gal and Hayoun, Avi and Mizrahi, Lior and Weiss, Gera}, title = {{Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {5:1--5:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.5}, URN = {urn:nbn:de:0030-drops-171964}, doi = {10.4230/LIPIcs.DISC.2022.5}, annote = {Keywords: Snapshot, Linearizability, Verification, Formal Methods} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The Complexity of Computing Optimum Labelings for Temporal Connectivity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 62:1-62:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{klobas_et_al:LIPIcs.MFCS.2022.62, author = {Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.}, title = {{The Complexity of Computing Optimum Labelings for Temporal Connectivity}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {62:1--62:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.62}, URN = {urn:nbn:de:0030-drops-168603}, doi = {10.4230/LIPIcs.MFCS.2022.62}, annote = {Keywords: Temporal graph, graph labeling, foremost temporal path, temporal connectivity, Steiner Tree} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Paul G. Spirakis. Algorithmic Problems on Temporal Graphs (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{spirakis:LIPIcs.SAND.2022.2, author = {Spirakis, Paul G.}, title = {{Algorithmic Problems on Temporal Graphs}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.2}, URN = {urn:nbn:de:0030-drops-159446}, doi = {10.4230/LIPIcs.SAND.2022.2}, annote = {Keywords: Temporal graph, stochastic temporal graph, vertex cover, temporal transitivity} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis. MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 28:1-28:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{nikoletseas_et_al:LIPIcs.ISAAC.2021.28, author = {Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul}, title = {{MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.28}, URN = {urn:nbn:de:0030-drops-154612}, doi = {10.4230/LIPIcs.ISAAC.2021.28}, annote = {Keywords: Random Intersection Graphs, Maximum Cut, Discrepancy} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 75:1-75:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{mertzios_et_al:LIPIcs.MFCS.2021.75, author = {Mertzios, George B. and Molter, Hendrik and Renken, Malte and Spirakis, Paul G. and Zschoche, Philipp}, title = {{The Complexity of Transitively Orienting Temporal Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {75:1--75:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.75}, URN = {urn:nbn:de:0030-drops-145157}, doi = {10.4230/LIPIcs.MFCS.2021.75}, annote = {Keywords: Temporal graph, transitive orientation, transitive closure, polynomial-time algorithm, NP-hardness, satisfiability} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 27:1-27:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{deligkas_et_al:LIPIcs.MFCS.2020.27, author = {Deligkas, Argyrios and Mertzios, George B. and Spirakis, Paul G. and Zamaraev, Viktor}, title = {{Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {27:1--27:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.27}, URN = {urn:nbn:de:0030-drops-126953}, doi = {10.4230/LIPIcs.MFCS.2020.27}, annote = {Keywords: Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm} }
Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)
Dmytro Antypov, Argyrios Deligkas, Vladimir Gusev, Matthew J. Rosseinsky, Paul G. Spirakis, and Michail Theofilatos. Crystal Structure Prediction via Oblivious Local Search. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 21:1-21:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{antypov_et_al:LIPIcs.SEA.2020.21, author = {Antypov, Dmytro and Deligkas, Argyrios and Gusev, Vladimir and Rosseinsky, Matthew J. and Spirakis, Paul G. and Theofilatos, Michail}, title = {{Crystal Structure Prediction via Oblivious Local Search}}, booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-148-1}, ISSN = {1868-8969}, year = {2020}, volume = {160}, editor = {Faro, Simone and Cantone, Domenico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.21}, URN = {urn:nbn:de:0030-drops-120950}, doi = {10.4230/LIPIcs.SEA.2020.21}, annote = {Keywords: crystal structure prediction, local search, combinatorial neighborhood} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Walter Hussak and Amitabh Trehan. On the Termination of Flooding. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 17:1-17:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{hussak_et_al:LIPIcs.STACS.2020.17, author = {Hussak, Walter and Trehan, Amitabh}, title = {{On the Termination of Flooding}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {17:1--17:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.17}, URN = {urn:nbn:de:0030-drops-118786}, doi = {10.4230/LIPIcs.STACS.2020.17}, annote = {Keywords: Flooding algorithm, Network algorithms, Distributed algorithms, Graph theory, Termination, Bipartiteness, Communication, Broadcast} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Michael Blondin, Javier Esparza, and Stefan Jaax. Expressive Power of Broadcast Consensus Protocols. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blondin_et_al:LIPIcs.CONCUR.2019.31, author = {Blondin, Michael and Esparza, Javier and Jaax, Stefan}, title = {{Expressive Power of Broadcast Consensus Protocols}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.31}, URN = {urn:nbn:de:0030-drops-109330}, doi = {10.4230/LIPIcs.CONCUR.2019.31}, annote = {Keywords: population protocols, complexity theory, counter machines, distributed computing} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Manfred Droste and Paul Gastin. Aperiodic Weighted Automata and Weighted First-Order Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{droste_et_al:LIPIcs.MFCS.2019.76, author = {Droste, Manfred and Gastin, Paul}, title = {{Aperiodic Weighted Automata and Weighted First-Order Logic}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {76:1--76:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.76}, URN = {urn:nbn:de:0030-drops-110203}, doi = {10.4230/LIPIcs.MFCS.2019.76}, annote = {Keywords: Weighted automata, weighted logic, aperiodic automata, first-order logic, unambiguous, finitely ambiguous, polynomially ambiguous} }
Feedback for Dagstuhl Publishing