Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Manuel Cáceres. Minimum Chain Cover in Almost Linear Time. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 31:1-31:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{caceres:LIPIcs.ICALP.2023.31, author = {C\'{a}ceres, Manuel}, title = {{Minimum Chain Cover in Almost Linear Time}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {31:1--31:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.31}, URN = {urn:nbn:de:0030-drops-180834}, doi = {10.4230/LIPIcs.ICALP.2023.31}, annote = {Keywords: Minimum chain cover, directed acyclic graph, minimum flow, flow decomposition, mergeable dictionaries, amortized running time} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Manuel Cáceres. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{caceres:LIPIcs.CPM.2023.7, author = {C\'{a}ceres, Manuel}, title = {{Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {7:1--7:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.7}, URN = {urn:nbn:de:0030-drops-179619}, doi = {10.4230/LIPIcs.CPM.2023.7}, annote = {Keywords: string matching, parameterized algorithms, FPT inside P, string algorithms, graph algorithms, directed acyclic graphs, labeled graphs, funnels} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Massimo Cairo, Shahbaz Khan, Romeo Rizzi, Sebastian Schmidt, Alexandru I. Tomescu, and Elia C. Zirondelli. Cut Paths and Their Remainder Structure, with Applications. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cairo_et_al:LIPIcs.STACS.2023.17, author = {Cairo, Massimo and Khan, Shahbaz and Rizzi, Romeo and Schmidt, Sebastian and Tomescu, Alexandru I. and Zirondelli, Elia C.}, title = {{Cut Paths and Their Remainder Structure, with Applications}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {17:1--17: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.17}, URN = {urn:nbn:de:0030-drops-176690}, doi = {10.4230/LIPIcs.STACS.2023.17}, annote = {Keywords: reachability, cut arc, strong bridge, covering walk, safety, persistence, essentiality, genome assembly} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Manuel Cáceres, Massimo Cairo, Andreas Grigorjew, Shahbaz Khan, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu, and Lucia Williams. Width Helps and Hinders Splitting Flows. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{caceres_et_al:LIPIcs.ESA.2022.31, author = {C\'{a}ceres, Manuel and Cairo, Massimo and Grigorjew, Andreas and Khan, Shahbaz and Mumey, Brendan and Rizzi, Romeo and Tomescu, Alexandru I. and Williams, Lucia}, title = {{Width Helps and Hinders Splitting Flows}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.31}, URN = {urn:nbn:de:0030-drops-169695}, doi = {10.4230/LIPIcs.ESA.2022.31}, annote = {Keywords: Flow decomposition, approximation algorithms, graph width} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Shahbaz Khan and Alexandru I. Tomescu. Optimizing Safe Flow Decompositions in DAGs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 72:1-72:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{khan_et_al:LIPIcs.ESA.2022.72, author = {Khan, Shahbaz and Tomescu, Alexandru I.}, title = {{Optimizing Safe Flow Decompositions in DAGs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {72:1--72:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.72}, URN = {urn:nbn:de:0030-drops-170101}, doi = {10.4230/LIPIcs.ESA.2022.72}, annote = {Keywords: safety, flows, networks, directed acyclic graphs} }
Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)
Leena Salmela. Efficient Solutions to Biological Problems Using de Bruijn Graphs (Invited Talk). In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{salmela:LIPIcs.WABI.2022.1, author = {Salmela, Leena}, title = {{Efficient Solutions to Biological Problems Using de Bruijn Graphs}}, booktitle = {22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)}, pages = {1:1--1:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-243-3}, ISSN = {1868-8969}, year = {2022}, volume = {242}, editor = {Boucher, Christina and Rahmann, Sven}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.1}, URN = {urn:nbn:de:0030-drops-170357}, doi = {10.4230/LIPIcs.WABI.2022.1}, annote = {Keywords: de Bruijn graph, variable order de Bruijn graph, genome assembly, sequencing error correction, k-mers} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Massimo Equi, Tuukka Norri, Jarno Alanko, Bastien Cazaux, Alexandru I. Tomescu, and Veli Mäkinen. Algorithms and Complexity on Indexing Elastic Founder Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{equi_et_al:LIPIcs.ISAAC.2021.20, author = {Equi, Massimo and Norri, Tuukka and Alanko, Jarno and Cazaux, Bastien and Tomescu, Alexandru I. and M\"{a}kinen, Veli}, title = {{Algorithms and Complexity on Indexing Elastic Founder Graphs}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {20:1--20:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.20}, URN = {urn:nbn:de:0030-drops-154532}, doi = {10.4230/LIPIcs.ISAAC.2021.20}, annote = {Keywords: orthogonal vectors hypothesis, multiple sequence alignment, segmentation} }
Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Lucia Williams, Alexandru I. Tomescu, and Brendan Mumey. Flow Decomposition with Subpath Constraints. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{williams_et_al:LIPIcs.WABI.2021.16, author = {Williams, Lucia and Tomescu, Alexandru I. and Mumey, Brendan}, title = {{Flow Decomposition with Subpath Constraints}}, booktitle = {21st International Workshop on Algorithms in Bioinformatics (WABI 2021)}, pages = {16:1--16:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-200-6}, ISSN = {1868-8969}, year = {2021}, volume = {201}, editor = {Carbone, Alessandra and El-Kebir, Mohammed}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.16}, URN = {urn:nbn:de:0030-drops-143695}, doi = {10.4230/LIPIcs.WABI.2021.16}, annote = {Keywords: Flow decomposition, subpath constraints, RNA-Seq} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu, and Elia C. Zirondelli. Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cairo_et_al:LIPIcs.ICALP.2021.43, author = {Cairo, Massimo and Rizzi, Romeo and Tomescu, Alexandru I. and Zirondelli, Elia C.}, title = {{Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {43:1--43:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.43}, URN = {urn:nbn:de:0030-drops-141122}, doi = {10.4230/LIPIcs.ICALP.2021.43}, annote = {Keywords: Graph algorithm, strong connectivity, reachability under failures} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Shahbaz Khan. Optimal Construction of Hierarchical Overlap Graphs. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{khan:LIPIcs.CPM.2021.17, author = {Khan, Shahbaz}, title = {{Optimal Construction of Hierarchical Overlap Graphs}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {17:1--17:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.17}, URN = {urn:nbn:de:0030-drops-139683}, doi = {10.4230/LIPIcs.CPM.2021.17}, annote = {Keywords: Hierarchical Overlap Graphs, String algorithms, Genome assembly} }
Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)
Veli Mäkinen, Bastien Cazaux, Massimo Equi, Tuukka Norri, and Alexandru I. Tomescu. Linear Time Construction of Indexable Founder Block Graphs. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{makinen_et_al:LIPIcs.WABI.2020.7, author = {M\"{a}kinen, Veli and Cazaux, Bastien and Equi, Massimo and Norri, Tuukka and Tomescu, Alexandru I.}, title = {{Linear Time Construction of Indexable Founder Block Graphs}}, booktitle = {20th International Workshop on Algorithms in Bioinformatics (WABI 2020)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-161-0}, ISSN = {1868-8969}, year = {2020}, volume = {172}, editor = {Kingsford, Carl and Pisanti, Nadia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.7}, URN = {urn:nbn:de:0030-drops-127961}, doi = {10.4230/LIPIcs.WABI.2020.7}, annote = {Keywords: Pangenome indexing, founder reconstruction, multiple sequence alignment, compressed data structures, string matching} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Massimo Equi, Roberto Grossi, Veli Mäkinen, and Alexandru I. Tomescu. On the Complexity of String Matching for Graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{equi_et_al:LIPIcs.ICALP.2019.55, author = {Equi, Massimo and Grossi, Roberto and M\"{a}kinen, Veli and Tomescu, Alexandru I.}, title = {{On the Complexity of String Matching for Graphs}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.55}, URN = {urn:nbn:de:0030-drops-106314}, doi = {10.4230/LIPIcs.ICALP.2019.55}, annote = {Keywords: exact pattern matching, graph query, graph search, labeled graphs, string matching, string search, strong exponential time hypothesis, heterogeneous networks, variation graphs} }
Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Niko Kiirala, Leena Salmela, and Alexandru I. Tomescu. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kiirala_et_al:LIPIcs.CPM.2019.8, author = {Kiirala, Niko and Salmela, Leena and Tomescu, Alexandru I.}, title = {{Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.8}, URN = {urn:nbn:de:0030-drops-104794}, doi = {10.4230/LIPIcs.CPM.2019.8}, annote = {Keywords: RNA secondary structure, RNA folding, Safe solution, Safe and complete algorithm, Counting problem} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi, and Alexandru I. Tomescu. Optimal Omnitig Listing for Safe and Complete Contig Assembly. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{cairo_et_al:LIPIcs.CPM.2017.29, author = {Cairo, Massimo and Medvedev, Paul and Obscura Acosta, Nidia and Rizzi, Romeo and Tomescu, Alexandru I.}, title = {{Optimal Omnitig Listing for Safe and Complete Contig Assembly}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {29:1--29:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.29}, URN = {urn:nbn:de:0030-drops-73423}, doi = {10.4230/LIPIcs.CPM.2017.29}, annote = {Keywords: genome assembly, graph algorithm, edge-covering walk, strong bridge} }
Feedback for Dagstuhl Publishing