LIPIcs, Volume 212
ISAAC 2021, December 6-8, 2021, Fukuoka, Japan
Editors: Hee-Kap Ahn and Kunihiko Sadakane
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Nico Bertram, Johannes Fischer, and Lukas Nalbach. Move-r: Optimizing the r-index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bertram_et_al:LIPIcs.SEA.2024.1, author = {Bertram, Nico and Fischer, Johannes and Nalbach, Lukas}, title = {{Move-r: Optimizing the r-index}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {1:1--1:19}, 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.1}, URN = {urn:nbn:de:0030-drops-203662}, doi = {10.4230/LIPIcs.SEA.2024.1}, annote = {Keywords: Compressed Text Index, Burrows-Wheeler Transform} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Paolo Boldi, Stefano Marchini, and Sebastiano Vigna. Engineering Zuffix Arrays. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boldi_et_al:LIPIcs.SEA.2024.2, author = {Boldi, Paolo and Marchini, Stefano and Vigna, Sebastiano}, title = {{Engineering Zuffix Arrays}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {2:1--2:18}, 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.2}, URN = {urn:nbn:de:0030-drops-203677}, doi = {10.4230/LIPIcs.SEA.2024.2}, annote = {Keywords: Suffix trees, suffix arrays, z-fast tries} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Patrick Dinklage, Johannes Fischer, and Nicola Prezza. Top-k Frequent Patterns in Streams and Parameterized-Space LZ Compression. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dinklage_et_al:LIPIcs.SEA.2024.9, author = {Dinklage, Patrick and Fischer, Johannes and Prezza, Nicola}, title = {{Top-k Frequent Patterns in Streams and Parameterized-Space LZ Compression}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-203748}, doi = {10.4230/LIPIcs.SEA.2024.9}, annote = {Keywords: compression, streaming, heavy hitters, algorithm engineering} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{balakrishnan_et_al:LIPIcs.SWAT.2024.4, author = {Balakrishnan, Girish and Chakraborty, Sankardeep and Narayanaswamy, N. S. and Sadakane, Kunihiko}, title = {{Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {4:1--4:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.4}, URN = {urn:nbn:de:0030-drops-200446}, doi = {10.4230/LIPIcs.SWAT.2024.4}, annote = {Keywords: succinct data structure, chordal graphs, leafage, vertex leafage, path graphs} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama. Shortest Beer Path Queries Based on Graph Decomposition. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2023.37, author = {Hanaka, Tesshu and Ono, Hirotaka and Sadakane, Kunihiko and Sugiyama, Kosuke}, title = {{Shortest Beer Path Queries Based on Graph Decomposition}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-193397}, doi = {10.4230/LIPIcs.ISAAC.2023.37}, annote = {Keywords: graph algorithm, shortest path problem, SPQR tree} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kunihiko Sadakane. Succinct Representations of Graphs (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{sadakane:LIPIcs.ISAAC.2022.1, author = {Sadakane, Kunihiko}, title = {{Succinct Representations of Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.1}, URN = {urn:nbn:de:0030-drops-172865}, doi = {10.4230/LIPIcs.ISAAC.2022.1}, annote = {Keywords: Graph Enumeration, Succinct Data Structure, Compression} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Sharma V. Thankachan. Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc. (Invited Talk). In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{thankachan:LIPIcs.CPM.2022.3, author = {Thankachan, Sharma V.}, title = {{Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc.}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {3:1--3:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.3}, URN = {urn:nbn:de:0030-drops-161300}, doi = {10.4230/LIPIcs.CPM.2022.3}, annote = {Keywords: Text Indexing, Suffix Trees, String Matching} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Yuma Arakawa, Gonzalo Navarro, and Kunihiko Sadakane. Bi-Directional r-Indexes. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{arakawa_et_al:LIPIcs.CPM.2022.11, author = {Arakawa, Yuma and Navarro, Gonzalo and Sadakane, Kunihiko}, title = {{Bi-Directional r-Indexes}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.11}, URN = {urn:nbn:de:0030-drops-161386}, doi = {10.4230/LIPIcs.CPM.2022.11}, annote = {Keywords: Compressed text indexes, Burrows-Wheeler Transform, highly repetitive text collections} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Space-Efficient Data Structure for Posets with Applications. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{yanagita_et_al:LIPIcs.SWAT.2022.33, author = {Yanagita, Tatsuya and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao}, title = {{Space-Efficient Data Structure for Posets with Applications}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {33:1--33:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.33}, URN = {urn:nbn:de:0030-drops-161931}, doi = {10.4230/LIPIcs.SWAT.2022.33}, annote = {Keywords: Succinct Data Structures, Posets, Blockchain} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 1-1188, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Proceedings{ahn_et_al:LIPIcs.ISAAC.2021, title = {{LIPIcs, Volume 212, ISAAC 2021, Complete Volume}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {1--1188}, 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}, URN = {urn:nbn:de:0030-drops-154329}, doi = {10.4230/LIPIcs.ISAAC.2021}, annote = {Keywords: LIPIcs, Volume 212, ISAAC 2021, Complete Volume} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ahn_et_al:LIPIcs.ISAAC.2021.0, author = {Ahn, Hee-Kap and Sadakane, Kunihiko}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {0:i--0:xviii}, 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.0}, URN = {urn:nbn:de:0030-drops-154330}, doi = {10.4230/LIPIcs.ISAAC.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Tatiana Starikovskaya. Streaming Pattern Matching (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{starikovskaya:LIPIcs.ISAAC.2021.1, author = {Starikovskaya, Tatiana}, title = {{Streaming Pattern Matching}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-154345}, doi = {10.4230/LIPIcs.ISAAC.2021.1}, annote = {Keywords: Streaming algorithms, Pattern matching, Hamming distance, Edit distance} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Prosenjit Bose. Spanning Properties of Variants of the Delaunay Graph (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bose:LIPIcs.ISAAC.2021.2, author = {Bose, Prosenjit}, title = {{Spanning Properties of Variants of the Delaunay Graph}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-154352}, doi = {10.4230/LIPIcs.ISAAC.2021.2}, annote = {Keywords: Delaunay Graph, Geometric Graph, Graph Spanner} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3, author = {Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha}, title = {{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {3:1--3:15}, 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.3}, URN = {urn:nbn:de:0030-drops-154363}, doi = {10.4230/LIPIcs.ISAAC.2021.3}, annote = {Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions} }