Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Bingbing Hu, Evangelos Kosinas, and Adam Polak. Connectivity Oracles for Predictable Vertex Failures. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hu_et_al:LIPIcs.ESA.2024.72, author = {Hu, Bingbing and Kosinas, Evangelos and Polak, Adam}, title = {{Connectivity Oracles for Predictable Vertex Failures}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {72:1--72:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.72}, URN = {urn:nbn:de:0030-drops-211437}, doi = {10.4230/LIPIcs.ESA.2024.72}, annote = {Keywords: Data structures, graph connectivity, algorithms with predictions} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Thomas A. Henzinger, Nicolas Mazzocchi, and N. Ege Saraç. Strategic Dominance: A New Preorder for Nondeterministic Processes. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{henzinger_et_al:LIPIcs.CONCUR.2024.29, author = {Henzinger, Thomas A. and Mazzocchi, Nicolas and Sara\c{c}, N. Ege}, title = {{Strategic Dominance: A New Preorder for Nondeterministic Processes}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {29:1--29:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.29}, URN = {urn:nbn:de:0030-drops-208011}, doi = {10.4230/LIPIcs.CONCUR.2024.29}, annote = {Keywords: quantitative automata, refinement relation, resolver, strategy, history-determinism} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Łukasz Kamiński and Sławomir Lasota. Bi-Reachability in Petri Nets with Data. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kaminski_et_al:LIPIcs.CONCUR.2024.31, author = {Kami\'{n}ski, {\L}ukasz and Lasota, S{\l}awomir}, title = {{Bi-Reachability in Petri Nets with Data}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {31:1--31:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.31}, URN = {urn:nbn:de:0030-drops-208038}, doi = {10.4230/LIPIcs.CONCUR.2024.31}, annote = {Keywords: Petri nets, Petri nets with data, reachability, bi-reachability, reversible reachability, mutual reachability, orbit-finite sets} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Simon Prucker and Lutz Schröder. Nominal Tree Automata with Name Allocation. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{prucker_et_al:LIPIcs.CONCUR.2024.35, author = {Prucker, Simon and Schr\"{o}der, Lutz}, title = {{Nominal Tree Automata with Name Allocation}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {35:1--35:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.35}, URN = {urn:nbn:de:0030-drops-208071}, doi = {10.4230/LIPIcs.CONCUR.2024.35}, annote = {Keywords: Data languages, tree automata, nominal automata, inclusion checking} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Symmetric-Difference (Degeneracy) and Signed Tree Models. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bonnet_et_al:LIPIcs.MFCS.2024.32, author = {Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor}, title = {{Symmetric-Difference (Degeneracy) and Signed Tree Models}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {32:1--32:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.32}, URN = {urn:nbn:de:0030-drops-205886}, doi = {10.4230/LIPIcs.MFCS.2024.32}, annote = {Keywords: symmetric difference, degeneracy, adjacency labeling schemes, NP-hardness} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Anuj Dawar and Ioannis Eleftheriadis. Preservation Theorems on Sparse Classes Revisited. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dawar_et_al:LIPIcs.MFCS.2024.47, author = {Dawar, Anuj and Eleftheriadis, Ioannis}, title = {{Preservation Theorems on Sparse Classes Revisited}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {47:1--47:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.47}, URN = {urn:nbn:de:0030-drops-206036}, doi = {10.4230/LIPIcs.MFCS.2024.47}, annote = {Keywords: Homomorphism preservation, sparsity, finite model theory, planar graphs} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Petr Hliněný and Jan Jedelský. ℋ-Clique-Width and a Hereditary Analogue of Product Structure. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hlineny_et_al:LIPIcs.MFCS.2024.61, author = {Hlin\v{e}n\'{y}, Petr and Jedelsk\'{y}, Jan}, title = {{ℋ-Clique-Width and a Hereditary Analogue of Product Structure}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {61:1--61:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.61}, URN = {urn:nbn:de:0030-drops-206176}, doi = {10.4230/LIPIcs.MFCS.2024.61}, annote = {Keywords: product structure, hereditary class, clique-width, twin-width} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Daniel Kráľ, Kristýna Pekárková, and Kenny Štorgel. Twin-Width of Graphs on Surfaces. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kral_et_al:LIPIcs.MFCS.2024.66, author = {Kr\'{a}\v{l}, Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na and \v{S}torgel, Kenny}, title = {{Twin-Width of Graphs on Surfaces}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {66:1--66:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.66}, URN = {urn:nbn:de:0030-drops-206226}, doi = {10.4230/LIPIcs.MFCS.2024.66}, annote = {Keywords: twin-width, graphs on surfaces, fixed parameter tractability} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2024.53, author = {Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.}, title = {{Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-201968}, doi = {10.4230/LIPIcs.ICALP.2024.53}, annote = {Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bougeret_et_al:LIPIcs.ICALP.2024.33, author = {Bougeret, Marin and Jansen, Bart M. P. and Sau, Ignasi}, title = {{Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {33:1--33: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.33}, URN = {urn:nbn:de:0030-drops-201766}, doi = {10.4230/LIPIcs.ICALP.2024.33}, annote = {Keywords: hitting subgraphs, hitting induced subgraphs, parameterized complexity, polynomial kernel, complexity dichotomy, elimination distance} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Martin Grohe and Daniel Neuen. Isomorphism for Tournaments of Small Twin Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grohe_et_al:LIPIcs.ICALP.2024.78, author = {Grohe, Martin and Neuen, Daniel}, title = {{Isomorphism for Tournaments of Small Twin Width}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {78:1--78: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.78}, URN = {urn:nbn:de:0030-drops-202216}, doi = {10.4230/LIPIcs.ICALP.2024.78}, annote = {Keywords: tournament isomorphism, twin width, fixed-parameter tractability, Weisfeiler-Leman algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yaowei Long and Yunfan Wang. Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 109:1-109:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{long_et_al:LIPIcs.ICALP.2024.109, author = {Long, Yaowei and Wang, Yunfan}, title = {{Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {109:1--109: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.109}, URN = {urn:nbn:de:0030-drops-202523}, doi = {10.4230/LIPIcs.ICALP.2024.109}, annote = {Keywords: connectivity, sensitivity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
C. Aiswarya, Amaldev Manuel, and Saina Sunny. Edit Distance of Finite State Transducers. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 125:1-125:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aiswarya_et_al:LIPIcs.ICALP.2024.125, author = {Aiswarya, C. and Manuel, Amaldev and Sunny, Saina}, title = {{Edit Distance of Finite State Transducers}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {125:1--125: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.125}, URN = {urn:nbn:de:0030-drops-202682}, doi = {10.4230/LIPIcs.ICALP.2024.125}, annote = {Keywords: transducers, edit distance, conjugacy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Jakub Gajarský and Rose McCarty. On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 137:1-137:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2024.137, author = {Gajarsk\'{y}, Jakub and McCarty, Rose}, title = {{On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {137:1--137: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.137}, URN = {urn:nbn:de:0030-drops-202802}, doi = {10.4230/LIPIcs.ICALP.2024.137}, annote = {Keywords: First-order model checking, structural graph theory, structural sparsity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Jakub Rydval. Homogeneity and Homogenizability: Hard Problems for the Logic SNP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 150:1-150:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{rydval:LIPIcs.ICALP.2024.150, author = {Rydval, Jakub}, title = {{Homogeneity and Homogenizability: Hard Problems for the Logic SNP}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {150:1--150: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.150}, URN = {urn:nbn:de:0030-drops-202939}, doi = {10.4230/LIPIcs.ICALP.2024.150}, annote = {Keywords: constraint satisfaction problems, finitely bounded, homogeneous, amalgamation property, universal, SNP, homogenizable} }
Feedback for Dagstuhl Publishing