LIPIcs, Volume 257
SAND 2023, June 19-21, 2023, Pisa, Italy
Editors: David Doty and Paul Spirakis
LIPIcs, Volume 117
MFCS 2018, August 27-31, 2018, Liverpool, GB
Editors: Igor Potapov, Paul Spirakis, and James Worrell
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kumamoto_et_al:LIPIcs.AofA.2024.22, author = {Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki}, title = {{The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.22}, URN = {urn:nbn:de:0030-drops-204577}, doi = {10.4230/LIPIcs.AofA.2024.22}, annote = {Keywords: Random walk, dynamic graph, recurrence, transience, coupling} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit}, title = {{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {16:1--16:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16}, URN = {urn:nbn:de:0030-drops-201598}, doi = {10.4230/LIPIcs.ICALP.2024.16}, annote = {Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dogeas_et_al:LIPIcs.ICALP.2024.55, author = {Dogeas, Konstantinos and Erlebach, Thomas and Kammer, Frank and Meintrup, Johannes and Moses Jr., William K.}, title = {{Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {55:1--55:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.55}, URN = {urn:nbn:de:0030-drops-201989}, doi = {10.4230/LIPIcs.ICALP.2024.55}, annote = {Keywords: dynamic graphs, parameterized algorithms, algorithmic graph theory, graph automorphism, orbit number} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Andreas Björklund, Petteri Kaski, and Jesper Nederlof. Another Hamiltonian Cycle in Bipartite Pfaffian Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2024.26, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Nederlof, Jesper}, title = {{Another Hamiltonian Cycle in Bipartite Pfaffian Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {26:1--26:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.26}, URN = {urn:nbn:de:0030-drops-201692}, doi = {10.4230/LIPIcs.ICALP.2024.26}, annote = {Keywords: Another Hamiltonian cycle, Pfaffian graph, planar graph, Thomason’s lollipop method} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sophia Heimann, Hung P. Hoang, and Stefan Hougardy. The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 84:1-84:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heimann_et_al:LIPIcs.ICALP.2024.84, author = {Heimann, Sophia and Hoang, Hung P. and Hougardy, Stefan}, title = {{The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {84:1--84:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.84}, URN = {urn:nbn:de:0030-drops-202270}, doi = {10.4230/LIPIcs.ICALP.2024.84}, annote = {Keywords: Traveling Salesman Problem, k-Opt algorithm, PLS-completeness} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Arnaud Carayol and Lucien Charamond. The Structure of Trees in the Pushdown Hierarchy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 131:1-131:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carayol_et_al:LIPIcs.ICALP.2024.131, author = {Carayol, Arnaud and Charamond, Lucien}, title = {{The Structure of Trees in the Pushdown Hierarchy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {131:1--131:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.131}, URN = {urn:nbn:de:0030-drops-202749}, doi = {10.4230/LIPIcs.ICALP.2024.131}, annote = {Keywords: Pushdown hierarchy, Monadic second-order logic, Automatic numbers} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Amina Doumane, Samuel Humeau, and Damien Pous. A Finite Presentation of Graphs of Treewidth at Most Three. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 135:1-135:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doumane_et_al:LIPIcs.ICALP.2024.135, author = {Doumane, Amina and Humeau, Samuel and Pous, Damien}, title = {{A Finite Presentation of Graphs of Treewidth at Most Three}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {135:1--135:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.135}, URN = {urn:nbn:de:0030-drops-202787}, doi = {10.4230/LIPIcs.ICALP.2024.135}, annote = {Keywords: Graphs, treewidth, connectedness, axiomatisation, series-parallel expressions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yuxi Fu, Qizhe Yang, and Yangluo Zheng. Improved Algorithm for Reachability in d-VASS. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 136:1-136:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fu_et_al:LIPIcs.ICALP.2024.136, author = {Fu, Yuxi and Yang, Qizhe and Zheng, Yangluo}, title = {{Improved Algorithm for Reachability in d-VASS}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {136:1--136:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.136}, URN = {urn:nbn:de:0030-drops-202799}, doi = {10.4230/LIPIcs.ICALP.2024.136}, annote = {Keywords: Petri net, vector addition system, reachability} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Wojciech Różowski. A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 149:1-149:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{rozowski:LIPIcs.ICALP.2024.149, author = {R\'{o}\.{z}owski, Wojciech}, title = {{A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {149:1--149:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.149}, URN = {urn:nbn:de:0030-drops-202920}, doi = {10.4230/LIPIcs.ICALP.2024.149}, annote = {Keywords: Regular Expressions, Behavioural Distances, Quantitative Equational Theories} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. Temporal Graph Realization from Fastest Paths. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{klobas_et_al:LIPIcs.SAND.2024.16, author = {Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.}, title = {{Temporal Graph Realization from Fastest Paths}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {16:1--16:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.16}, URN = {urn:nbn:de:0030-drops-198945}, doi = {10.4230/LIPIcs.SAND.2024.16}, annote = {Keywords: Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, parameterized complexity} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Duncan Adamson, Nathan Flaherty, Igor Potapov, and Paul G. Spirakis. Brief Announcement: Collision-Free Robot Scheduling. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 22:1-22:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{adamson_et_al:LIPIcs.SAND.2024.22, author = {Adamson, Duncan and Flaherty, Nathan and Potapov, Igor and Spirakis, Paul G.}, title = {{Brief Announcement: Collision-Free Robot Scheduling}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {22:1--22:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.22}, URN = {urn:nbn:de:0030-drops-199004}, doi = {10.4230/LIPIcs.SAND.2024.22}, annote = {Keywords: Graph Exploration, Scheduling, NP-Completeness, Approximation Algorithms} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 27:1-27:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mertzios_et_al:LIPIcs.SAND.2024.27, author = {Mertzios, George B. and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul G.}, title = {{Brief Announcement: On the Existence of \delta-Temporal Cliques in Random Simple Temporal Graphs}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {27:1--27:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.27}, URN = {urn:nbn:de:0030-drops-199056}, doi = {10.4230/LIPIcs.SAND.2024.27}, annote = {Keywords: Simple random temporal graph, \delta-temporal clique, probabilistic method} }
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} }