LIPIcs, Volume 283
ISAAC 2023, December 3-6, 2023, Kyoto, Japan
Editors: Satoru Iwata and Naonori Kakimura
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Seok-Hee Hong. Faithful Graph Drawing (Invited Talk). In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hong:LIPIcs.ISAAC.2023.2, author = {Hong, Seok-Hee}, title = {{Faithful Graph Drawing}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.2}, URN = {urn:nbn:de:0030-drops-193044}, doi = {10.4230/LIPIcs.ISAAC.2023.2}, annote = {Keywords: Graph drawing, Planar graphs, Beyond planar graphs, Tutte’s barycenter theorem, Steinitz’s theorem, F\'{a}ry’s theorem, Sublinear-time graph drawing algorithm, Faithful graph drawing, Symmetric graph drawing} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Hugo A. Akitaya, Maike Buchin, Majid Mirzanezhad, Leonie Ryvkin, and Carola Wenk. Realizability of Free Spaces of Curves. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 3:1-3:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2023.3, author = {A. Akitaya, Hugo and Buchin, Maike and Mirzanezhad, Majid and Ryvkin, Leonie and Wenk, Carola}, title = {{Realizability of Free Spaces of Curves}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {3:1--3:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.3}, URN = {urn:nbn:de:0030-drops-193057}, doi = {10.4230/LIPIcs.ISAAC.2023.3}, annote = {Keywords: Fr\'{e}chet distance, Distance Geometry, free space diagram, inverse problem} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Duncan Adamson, Pamela Fleischmann, Annika Huch, Tore Koß, Florin Manea, and Dirk Nowotka. k-Universality of Regular Languages. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 4:1-4:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{adamson_et_al:LIPIcs.ISAAC.2023.4, author = {Adamson, Duncan and Fleischmann, Pamela and Huch, Annika and Ko{\ss}, Tore and Manea, Florin and Nowotka, Dirk}, title = {{k-Universality of Regular Languages}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {4:1--4:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.4}, URN = {urn:nbn:de:0030-drops-193064}, doi = {10.4230/LIPIcs.ISAAC.2023.4}, annote = {Keywords: String Algorithms, Regular Languages, Finite Automata, Subsequences} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Jungho Ahn, Jinha Kim, and O-joung Kwon. Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 5:1-5:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ahn_et_al:LIPIcs.ISAAC.2023.5, author = {Ahn, Jungho and Kim, Jinha and Kwon, O-joung}, title = {{Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.5}, URN = {urn:nbn:de:0030-drops-193072}, doi = {10.4230/LIPIcs.ISAAC.2023.5}, annote = {Keywords: kernelization, independent set, dominating set, covering, packing} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Henk Alkema and Mark de Berg. Geometric TSP on Sets. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 6:1-6:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{alkema_et_al:LIPIcs.ISAAC.2023.6, author = {Alkema, Henk and de Berg, Mark}, title = {{Geometric TSP on Sets}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.6}, URN = {urn:nbn:de:0030-drops-193083}, doi = {10.4230/LIPIcs.ISAAC.2023.6}, annote = {Keywords: Euclidean TSP, TSP on Sets, Rectilinear TSP, TSP on Neighbourhoods} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Kazuyuki Amano. Depth-Three Circuits for Inner Product and Majority Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 7:1-7:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{amano:LIPIcs.ISAAC.2023.7, author = {Amano, Kazuyuki}, title = {{Depth-Three Circuits for Inner Product and Majority Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.7}, URN = {urn:nbn:de:0030-drops-193092}, doi = {10.4230/LIPIcs.ISAAC.2023.7}, annote = {Keywords: Circuit complexity, depth-3 circuits, upper bounds, lower bounds, computer-assisted proof} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora, and Stéphane Vialette. Recognizing Unit Multiple Intervals Is Hard. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ardevolmartinez_et_al:LIPIcs.ISAAC.2023.8, author = {Ard\'{e}vol Mart{\'\i}nez, Virginia and Rizzi, Romeo and Sikora, Florian and Vialette, St\'{e}phane}, title = {{Recognizing Unit Multiple Intervals Is Hard}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.8}, URN = {urn:nbn:de:0030-drops-193102}, doi = {10.4230/LIPIcs.ISAAC.2023.8}, annote = {Keywords: Interval graphs, unit multiple interval graphs, recognition, NP-hardness} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual. Non-Clairvoyant Makespan Minimization Scheduling with Predictions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 9:1-9:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bampis_et_al:LIPIcs.ISAAC.2023.9, author = {Bampis, Evripidis and Kononov, Alexander and Lucarelli, Giorgio and Pascual, Fanny}, title = {{Non-Clairvoyant Makespan Minimization Scheduling with Predictions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.9}, URN = {urn:nbn:de:0030-drops-193114}, doi = {10.4230/LIPIcs.ISAAC.2023.9}, annote = {Keywords: scheduling, online, learning-augmented algorithm} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Gabriel Bathie, Tomasz Kociumaka, and Tatiana Starikovskaya. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 10:1-10:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bathie_et_al:LIPIcs.ISAAC.2023.10, author = {Bathie, Gabriel and Kociumaka, Tomasz and Starikovskaya, Tatiana}, title = {{Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.10}, URN = {urn:nbn:de:0030-drops-193124}, doi = {10.4230/LIPIcs.ISAAC.2023.10}, annote = {Keywords: Approximate pattern matching, streaming algorithms, palindromes, squares} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski. Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 11:1-11:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bergougnoux_et_al:LIPIcs.ISAAC.2023.11, author = {Bergougnoux, Benjamin and Gajarsk\'{y}, Jakub and Gu\'{s}piel, Grzegorz and Hlin\v{e}n\'{y}, Petr and Pokr\'{y}vka, Filip and Soko{\l}owski, Marek}, title = {{Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.11}, URN = {urn:nbn:de:0030-drops-193130}, doi = {10.4230/LIPIcs.ISAAC.2023.11}, annote = {Keywords: twin-width, tree-width, excluded grid, sparsity} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Giulia Bernardini, Gabriele Fici, Paweł Gawrychowski, and Solon P. Pissis. Substring Complexity in Sublinear Space. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 12:1-12:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bernardini_et_al:LIPIcs.ISAAC.2023.12, author = {Bernardini, Giulia and Fici, Gabriele and Gawrychowski, Pawe{\l} and Pissis, Solon P.}, title = {{Substring Complexity in Sublinear Space}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {12:1--12:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.12}, URN = {urn:nbn:de:0030-drops-193143}, doi = {10.4230/LIPIcs.ISAAC.2023.12}, annote = {Keywords: sublinear-space algorithm, string algorithm, substring complexity} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm. New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 13:1-13:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{berndt_et_al:LIPIcs.ISAAC.2023.13, author = {Berndt, Sebastian and Brinkop, Hauke and Jansen, Klaus and Mnich, Matthias and Stamm, Tobias}, title = {{New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.13}, URN = {urn:nbn:de:0030-drops-193155}, doi = {10.4230/LIPIcs.ISAAC.2023.13}, annote = {Keywords: Integer programming, scheduling algorithms, uniformly related machines, makespan minimization} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Jannis Blauth, Meike Neuwohner, Luise Puhlmann, and Jens Vygen. Improved Guarantees for the a Priori TSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 14:1-14:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{blauth_et_al:LIPIcs.ISAAC.2023.14, author = {Blauth, Jannis and Neuwohner, Meike and Puhlmann, Luise and Vygen, Jens}, title = {{Improved Guarantees for the a Priori TSP}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.14}, URN = {urn:nbn:de:0030-drops-193161}, doi = {10.4230/LIPIcs.ISAAC.2023.14}, annote = {Keywords: A priori TSP, random sampling, stochastic combinatorial optimization} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Michaela Borzechowski, Patrick Schnider, and Simon Weber. An FPT Algorithm for Splitting a Necklace Among Two Thieves. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 15:1-15:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{borzechowski_et_al:LIPIcs.ISAAC.2023.15, author = {Borzechowski, Michaela and Schnider, Patrick and Weber, Simon}, title = {{An FPT Algorithm for Splitting a Necklace Among Two Thieves}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.15}, URN = {urn:nbn:de:0030-drops-193178}, doi = {10.4230/LIPIcs.ISAAC.2023.15}, annote = {Keywords: Necklace splitting, n-separability, well-separation, ham sandwich, FPT} }
Feedback for Dagstuhl Publishing