Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)
Giovanni Buzzega, Alessio Conte, Roberto Grossi, and Giulia Punzi. McDag: Indexing Maximal Common Subsequences in Practice. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{buzzega_et_al:LIPIcs.WABI.2024.21, author = {Buzzega, Giovanni and Conte, Alessio and Grossi, Roberto and Punzi, Giulia}, title = {{McDag: Indexing Maximal Common Subsequences in Practice}}, booktitle = {24th International Workshop on Algorithms in Bioinformatics (WABI 2024)}, pages = {21:1--21:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-340-9}, ISSN = {1868-8969}, year = {2024}, volume = {312}, editor = {Pissis, Solon P. and Sung, Wing-Kin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.21}, URN = {urn:nbn:de:0030-drops-206650}, doi = {10.4230/LIPIcs.WABI.2024.21}, annote = {Keywords: Index data structure, DAG, Common subsequence, Inclusion-wise maximality, LCS} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ilan Doron-Arad and Joseph (Seffi) Naor. Non-Linear Paging. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.57, author = {Doron-Arad, Ilan and Naor, Joseph (Seffi)}, title = {{Non-Linear Paging}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {57:1--57:19}, 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.57}, URN = {urn:nbn:de:0030-drops-202000}, doi = {10.4230/LIPIcs.ICALP.2024.57}, annote = {Keywords: paging, competitive analysis, non-linear paging, submodular and supermodular functions} }
Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)
Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, and Hiroki Arimura. Finding Diverse Strings and Longest Common Subsequences in a Graph. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{shida_et_al:LIPIcs.CPM.2024.27, author = {Shida, Yuto and Punzi, Giulia and Kobayashi, Yasuaki and Uno, Takeaki and Arimura, Hiroki}, title = {{Finding Diverse Strings and Longest Common Subsequences in a Graph}}, booktitle = {35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)}, pages = {27:1--27:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-326-3}, ISSN = {1868-8969}, year = {2024}, volume = {296}, editor = {Inenaga, Shunsuke and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.27}, URN = {urn:nbn:de:0030-drops-201370}, doi = {10.4230/LIPIcs.CPM.2024.27}, annote = {Keywords: Sequence analysis, longest common subsequence, Hamming distance, dispersion, approximation algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Alessio Conte, Roberto Grossi, Giulia Punzi, and Takeaki Uno. A Compact DAG for Storing and Searching Maximal Common Subsequences. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{conte_et_al:LIPIcs.ISAAC.2023.21, author = {Conte, Alessio and Grossi, Roberto and Punzi, Giulia and Uno, Takeaki}, title = {{A Compact DAG for Storing and Searching Maximal Common Subsequences}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {21:1--21: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.21}, URN = {urn:nbn:de:0030-drops-193231}, doi = {10.4230/LIPIcs.ISAAC.2023.21}, annote = {Keywords: Maximal common subsequence, DAG, Compact data structures, Enumeration, Constant amortized time, Random access} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, and Takeaki Uno. Optimal LZ-End Parsing Is Hard. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bannai_et_al:LIPIcs.CPM.2023.3, author = {Bannai, Hideo and Funakoshi, Mitsuru and Kurita, Kazuhiro and Nakashima, Yuto and Seto, Kazuhisa and Uno, Takeaki}, title = {{Optimal LZ-End Parsing Is Hard}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {3:1--3:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.3}, URN = {urn:nbn:de:0030-drops-179571}, doi = {10.4230/LIPIcs.CPM.2023.3}, annote = {Keywords: Data Compression, LZ-End, Repetitiveness measures} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka. Sorting Balls and Water: Equivalence and Computational Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ito_et_al:LIPIcs.FUN.2022.16, author = {Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Otachi, Yota and Saitoh, Toshiki and Suzuki, Akira and Uehara, Ryuhei and Uno, Takeaki and Yamanaka, Katsuhisa and Yoshinaka, Ryo}, title = {{Sorting Balls and Water: Equivalence and Computational Complexity}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.16}, URN = {urn:nbn:de:0030-drops-159867}, doi = {10.4230/LIPIcs.FUN.2022.16}, annote = {Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Alessio Conte, Roberto Grossi, Mamadou Moustapha Kanté, Andrea Marino, Takeaki Uno, and Kunihiro Wasa. Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{conte_et_al:LIPIcs.MFCS.2019.73, author = {Conte, Alessio and Grossi, Roberto and Kant\'{e}, Mamadou Moustapha and Marino, Andrea and Uno, Takeaki and Wasa, Kunihiro}, title = {{Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {73:1--73:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.73}, URN = {urn:nbn:de:0030-drops-110174}, doi = {10.4230/LIPIcs.MFCS.2019.73}, annote = {Keywords: Graph algorithms, enumeration, listing and counting, Steiner trees, induced subgraphs} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient Enumeration of Dominating Sets for Sparse Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kurita_et_al:LIPIcs.ISAAC.2018.8, author = {Kurita, Kazuhiro and Wasa, Kunihiro and Arimura, Hiroki and Uno, Takeaki}, title = {{Efficient Enumeration of Dominating Sets for Sparse Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.8}, URN = {urn:nbn:de:0030-drops-99560}, doi = {10.4230/LIPIcs.ISAAC.2018.8}, annote = {Keywords: Enumeration algorithm, polynomial amortized time, dominating set, girth, degeneracy} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Alessio Conte, Mamadou Moustapha Kanté, Takeaki Uno, and Kunihiro Wasa. On Maximal Cliques with Connectivity Constraints in Directed Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{conte_et_al:LIPIcs.ISAAC.2017.23, author = {Conte, Alessio and Kant\'{e}, Mamadou Moustapha and Uno, Takeaki and Wasa, Kunihiro}, title = {{On Maximal Cliques with Connectivity Constraints in Directed Graphs}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {23:1--23:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.23}, URN = {urn:nbn:de:0030-drops-82284}, doi = {10.4230/LIPIcs.ISAAC.2017.23}, annote = {Keywords: Enumeration algorithms, Bounded delay, Directed graphs, Community structure, Network analytics} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and Hardness of Token Swapping. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{miltzow_et_al:LIPIcs.ESA.2016.66, author = {Miltzow, Tillmann and Narins, Lothar and Okamoto, Yoshio and Rote, G\"{u}nter and Thomas, Antonis and Uno, Takeaki}, title = {{Approximation and Hardness of Token Swapping}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {66:1--66:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.66}, URN = {urn:nbn:de:0030-drops-64084}, doi = {10.4230/LIPIcs.ESA.2016.66}, annote = {Keywords: token swapping, minimum generator sequence, graph theory, NP-hardness, approximation algorithms} }
Feedback for Dagstuhl Publishing