Elastic founder graphs improved and enhanced. (English) Zbl 07809107
MSC:
68Qxx
Found 18 Documents (Results 1–18)
On the complexity of string matching for graphs. (English) Zbl 07753172
MSC:
68-XX
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. (English) Zbl 07741112
MSC:
68Qxx
Quantum time complexity and algorithms for pattern matching on labeled graphs. (English) Zbl 1525.68063
Arroyuelo, Diego (ed.) et al., String processing and information retrieval. 29th international symposium, SPIRE 2022, Concepción, Chile, November 8–10, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13617, 303-314 (2022).
Fast and optimal sequence-to-graph alignment guided by seeds. (English) Zbl 1496.92069
Pe’er, Itsik (ed.), Research in computational molecular biology. 26th annual international conference, RECOMB 2022, San Diego, CA, USA, May 22–25, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13278, 306-325 (2022).
The complexity of approximate pattern matching on de Bruijn graphs. (English) Zbl 1494.92086
Pe’er, Itsik (ed.), Research in computational molecular biology. 26th annual international conference, RECOMB 2022, San Diego, CA, USA, May 22–25, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13278, 263-278 (2022).
Linear time construction of indexable elastic founder graphs. (English) Zbl 07577720
Bazgan, Cristina (ed.) et al., Combinatorial algorithms. 33rd international workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13270, 480-493 (2022).
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. (English) Zbl 1490.68151
Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 608-622 (2021).
Wheeler languages. (English) Zbl 1518.68162
MSC:
68Q45
Succinct representations for (non)deterministic finite automata. (English) Zbl 07405977
Leporati, Alberto (ed.) et al., Language and automata theory and applications. 15th international conference, LATA 2021, Milan, Italy, March 1–5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12638, 55-67 (2021).
MSC:
68Q45
The fine-grained complexity of Median and center string problems under edit distance. (English) Zbl 07651200
Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 61, 19 p. (2020).
MSC:
68Wxx
Linear time construction of indexable founder block graphs. (English) Zbl 1515.92048
Kingsford, Carl (ed.) et al., 20th international workshop on algorithms in bioinformatics. WABI 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 172, Article 7, 18 p. (2020).
Complexity issues of string to graph approximate matching. (English) Zbl 1437.68208
Leporati, Alberto (ed.) et al., Language and automata theory and applications. 14th international conference, LATA 2020, Milan, Italy, March 4–6, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12038, 248-259 (2020).
Filter Results by …
Document Type
- Journal Articles (9)
- Collection Articles (9)
all
top 5
Author
- Mäkinen, Veli (7)
- Equi, Massimo (6)
- Tomescu, Alexandru Ioan (6)
- Gibney, Daniel (4)
- Thankachan, Sharma V. (4)
- Norri, Tuukka (3)
- Rizzo, Nicola (3)
- Alanko, Jarno (2)
- Cazaux, Bastien (2)
- Dondi, Riccardo (2)
- Grossi, Roberto (2)
- Mauri, Giancarlo (2)
- Policriti, Alberto (2)
- Zoppis, Italo (2)
- Aluru, Srinivas (1)
- Bentley, Jason W. (1)
- Bichsel, Benjamin (1)
- Casel, Katrin (1)
- Chakraborty, Sankardeep (1)
- D’Agostino, Giovanna (1)
- Darbari, Parisa (1)
- Hoppenworth, Gary (1)
- Ivanov, Pesho (1)
- Prezza, Nicola (1)
- Sadakane, Kunihiko (1)
- Satti, Srinivasa Rao (1)
- Schmid, Markus L. (1)
- Vechev, Martin T. (1)
Serial
- Algorithmica (3)
- Theor. Comput. Sci. (2)
- Inf. Comput. (2)
- Log. Methods Comput. Sci. (1)
- ACM Trans. Algorithms (1)
