LIPIcs, Volume 289
STACS 2024, March 12-14, 2024, Clermont-Ferrand, France
Editors: Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov
LIPIcs, Volume 254
STACS 2023, March 7-9, 2023, Hamburg, Germany
Editors: Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Philip Mayer and Petra Mutzel. Engineering A* Search for the Flip Distance of Plane Triangulations. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mayer_et_al:LIPIcs.SEA.2024.23, author = {Mayer, Philip and Mutzel, Petra}, title = {{Engineering A* Search for the Flip Distance of Plane Triangulations}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {23:1--23:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.23}, URN = {urn:nbn:de:0030-drops-203887}, doi = {10.4230/LIPIcs.SEA.2024.23}, annote = {Keywords: Computational Geometry, Triangulations, Flip Distance, A-star Search, Integer Linear Programming} }
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)
Narek Bojikian and Stefan Kratsch. A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bojikian_et_al:LIPIcs.ICALP.2024.29, author = {Bojikian, Narek and Kratsch, Stefan}, title = {{A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {29:1--29: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.29}, URN = {urn:nbn:de:0030-drops-201728}, doi = {10.4230/LIPIcs.ICALP.2024.29}, annote = {Keywords: Parameterized complexity, Steiner tree, clique-width} }
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 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 1-1048, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Proceedings{beyersdorff_et_al:LIPIcs.STACS.2024, title = {{LIPIcs, Volume 289, STACS 2024, Complete Volume}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {1--1048}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024}, URN = {urn:nbn:de:0030-drops-197098}, doi = {10.4230/LIPIcs.STACS.2024}, annote = {Keywords: LIPIcs, Volume 289, STACS 2024, Complete Volume} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{beyersdorff_et_al:LIPIcs.STACS.2024.0, author = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {0:i--0:xx}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.0}, URN = {urn:nbn:de:0030-drops-197108}, doi = {10.4230/LIPIcs.STACS.2024.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2023.18, author = {Bergougnoux, Benjamin and Chekan, Vera and Ganian, Robert and Kant\'{e}, Mamadou Moustapha and Mnich, Matthias and Oum, Sang-il and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan}, title = {{Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.18}, URN = {urn:nbn:de:0030-drops-186710}, doi = {10.4230/LIPIcs.ESA.2023.18}, annote = {Keywords: Parameterized complexity, shrubdepth, space complexity, algebraic methods} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 1-1026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Proceedings{berenbrink_et_al:LIPIcs.STACS.2023, title = {{LIPIcs, Volume 254, STACS 2023, Complete Volume}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {1--1026}, 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}, URN = {urn:nbn:de:0030-drops-176515}, doi = {10.4230/LIPIcs.STACS.2023}, annote = {Keywords: LIPIcs, Volume 254, STACS 2023, Complete Volume} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berenbrink_et_al:LIPIcs.STACS.2023.0, author = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {0:i--0:xxii}, 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.0}, URN = {urn:nbn:de:0030-drops-176525}, doi = {10.4230/LIPIcs.STACS.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof. Tight Lower Bounds for Problems Parameterized by Rank-Width. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bergougnoux_et_al:LIPIcs.STACS.2023.11, author = {Bergougnoux, Benjamin and Korhonen, Tuukka and Nederlof, Jesper}, title = {{Tight Lower Bounds for Problems Parameterized by Rank-Width}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {11:1--11:17}, 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.11}, URN = {urn:nbn:de:0030-drops-176636}, doi = {10.4230/LIPIcs.STACS.2023.11}, annote = {Keywords: rank-width, exponential time hypothesis, Boolean-width, parameterized algorithms, independent set, dominating set, maximum induced matching, feedback vertex set} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum. Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kante_et_al:LIPIcs.STACS.2022.40, author = {Kant\'{e}, Mamadou Moustapha and Kim, Eun Jung and Kwon, O-joung and Oum, Sang-il}, title = {{Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {40:1--40:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.40}, URN = {urn:nbn:de:0030-drops-158507}, doi = {10.4230/LIPIcs.STACS.2022.40}, annote = {Keywords: path-width, matroid, linear rank-width, graph, forbidden minor, vertex-minor, pivot-minor} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Mamadou Moustapha Kanté, Christophe Paul, and Dimitrios M. Thilikos. A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kante_et_al:LIPIcs.ESA.2020.64, author = {Kant\'{e}, Mamadou Moustapha and Paul, Christophe and Thilikos, Dimitrios M.}, title = {{A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {64:1--64:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.64}, URN = {urn:nbn:de:0030-drops-129307}, doi = {10.4230/LIPIcs.ESA.2020.64}, annote = {Keywords: Graph decompositions, Parameterized algorithms, Typical sequences, Pathwidth, Graph searching} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Benjamin Bergougnoux and Mamadou Moustapha Kanté. More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2019.17, author = {Bergougnoux, Benjamin and Kant\'{e}, Mamadou Moustapha}, title = {{More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.17}, URN = {urn:nbn:de:0030-drops-111383}, doi = {10.4230/LIPIcs.ESA.2019.17}, annote = {Keywords: connectivity problem, feedback vertex set, d-neighbor equivalence, \{sigma,rho\}-domination, clique-width, rank-width, mim-width} }